[Codility] MissingInteger

Problem

---

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가 있을 때, 0보다 큰 가장 작은 정수를 반환하는 함수를 작성하세요. 이 정수는 배열 A에는 존재하지 않아야 합니다.

예를 들어:

• 배열 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] 범위 내의 정수입니다.

 

Solution

---

이 문제는 배열 A에서 가장 작은 양의 정수를 찾는 문제입니다. 즉, 배열에 존재하지 않는 가장 작은 양의 정수를 반환해야 합니다.

class Solution {
    public int solution(int[] A) {
        // 배열 크기가 최대 100,000이므로 100,001 크기의 배열을 생성
        boolean[] seen = new boolean[100001];
        
        // 배열을 순회하면서 양의 정수만 기록
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0 && A[i] <= 100000) {
                seen[A[i]] = true; // 해당 숫자가 등장했음을 기록
            }
        }
        
        // 1부터 순차적으로 탐색하여 등장하지 않은 가장 작은 양의 정수를 찾음
        for (int i = 1; i <= 100000; i++) {
            if (!seen[i]) {
                return i;
            }
        }
        
        // 모두 등장했으면 100,001이 가장 작은 양의 정수가 됨
        return 100001;
    }
}

 

1. 음수와 0은 무시: 배열에 음수와 0은 무조건 양의 정수에 해당되지 않으므로, 우리는 양수만 고려합니다.
2. 범위 제한: 문제에서 배열 A에 있는 양의 정수는 최대 100,000까지의 크기를 가질 수 있으므로, 가장 작은 양의 정수는 항상 1부터 시작하게 됩니다.
3. 존재 확인을 위한 배열 사용: 배열의 크기가 최대 100,000이기 때문에, 각 정수의 존재 여부를 확인하는 데 O(N) 시간 복잡도를 가지는 간단한 배열을 사용할 수 있습니다.
   • 예를 들어, 1부터 100,000까지의 정수 범위에서 각 수가 등장했는지를 기록하는 배열 seen[]을 생성하고, A 배열을 순회하면서 해당 수가 등장했는지 체크합니다.
4. 결과 도출: seen[] 배열을 순회하면서 가장 작은 양의 정수 중 등장하지 않은 값을 찾으면 됩니다.