MissingInteger

🔗 문제 링크

https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/start/

❔ 문제 설명

This is a demo task.

Write a function:

def solution(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].

---

💡 풀이 (언어 : Java & Python)

비교적 무난하게 풀었다. 시간 복잡도는 $O(N)$ or $O(N * log(N))$이 나왔다.

Java

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {
        int answer = 0;
        Arrays.sort(A);
        for (int n : A) {
            if (n > 0) {
                if (n > answer + 1)
                    return answer + 1;
                else if (n == answer + 1)
                    answer++;
            }
        }
        return answer + 1;
    }
}

Python

def solution(A):
    # 중복을 제거하기위해 set 사용
    checkSet = set()

    for i in range(len(A)):
        # 0, 음수는 정답과 관련 없으므로 제외
        if A[i] >= 1:
            checkSet.add(A[i])
    # set를 list로 변환해 sort 함수로 정렬        
    answer = list(checkSet)
    answer.sort()
    
    for i in range(len(answer)):
        # i+1은 1부터 1씩 증가하므로 중간에 없으면 그때 i+1이 존재하지 않는 제일 작은 양의 정수
        if answer[i] != i+1:
            return i+1
    # 위의 반복문을 다 돌아도 없으면 중간에 빠진 양의 정수가 없는 것이므로 다음 큰 수가 답    
    return len(answer) + 1