codility - MissingInteger 자바 풀이

• 우선 처음에 든 생각이 (정렬후 탐색 / DP에 표시하기) 두가지 방법이였는데, 정렬후 탐색이 nlogn ~ n^2 이므로 메모리가 많이 들지만 안전하게 빠른 dp로 사용
  • 등장하는 숫자도 100만이라서 boolean배열로 125킬로바이트임. 등장하는 숫자가 더 크면 사용하기 힘든 방식이나, 이 문제에서는 사용하기 좋음
  • O(N * log(N)) 시간복잡도로 정렬한다면 가능할지ㄷ..?(안해봐서 모름)
• 입력으로 주어진 배열 A에서 등장하지않는 가장 작은 정수를 찾아야 하므로
• 등장한 index에 해당하는 dp배열에 true라고 표시
• 등장하지 않았다면 초기값인 false가 들어있을테니 작은순서로 순차탐색후 찾자마자 리턴!

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        boolean dp[] = new boolean[10000001];
        
        for(int n : A) {
            if(n>0) {
                dp[n] = true;
            }
        }
        
        for(int i=1 ; i<10000001 ; i++) {
            if(dp[i] == false) {
                return i;
            }
        }
        return -1;
    }
}