Codility_MissingInteger

4-4. MissingInteger

This is a demo task.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].

배열 A가 N개의 정수를 포함할 때,
배열 A에 존재하지 않는 가장 작은 양의 정수(0보다 큰)를 반환하는 함수를 작성

예를 들어,

A = [1, 3, 6, 4, 1, 2]가 주어지면, 함수는 5를 반환

A = [1, 2, 3]가 주어지면, 함수는 4를 반환

A = [−1, −3]가 주어지면, 함수는 1을 반환

N은 [1…100,000] 범위 내의 정수이며
배열 A의 각 요소는 [−1,000,000…1,000,000] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int aSize = A.length;
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < aSize; i++){
            set.add(A[i]);
        }
        // HashSet으로 중복된 수를 거름
        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        // List를 만들어 set으로 거른 수를 정렬(HashSet은 정렬이 불가능)
        int listSize = list.size();
        int result = 1; // 최소 반환값 1로 초기화
        for(int s = 0; s < listSize; s++){
            if(list.get(s) == result){// 중간에 빠진 수를 찾아야됨으로 result와 같다면
                result++; // +1을 해주고 그 다음 수를 체크함
            }
        }
        return result;
    }
}

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/