[코딜리티/Java] MissingInteger

N개의 숫자를 갖는 배열 A가 주어지는데, N개의 숫자 중 1부터 순차적으로 확인했을 때, 그 중 빠진 숫자 중 최소인 숫자를 반환하는 문제.

class Solution {
    public int solution(int[] A) {
    	// 1 ~ 1000000 범위이므로
        boolean[] map = new boolean[1000001];
        // 소팅하고
        Arrays.sort(A);
        // 만약 최대값도 음수이면 볼 필요 없이 그냥 1 반환
        if (A[A.length-1] < 0) {
            return 1;
        }
        // 양수인 값들만 있는 경우 true로
        for (int a : A) {
            if (a > 0) {
                map[a] = true;
            }
        }
        // 1부터 돌면서 false인 경우 빠진 케이스이므로 return
        for (int i = 1; i < map.length; i++) {
            if (!map[i]) {
                return i;
            }
        }
        return -1;
    }
}

우선 배열 A 값의 범위가 -1,000,000 ~ 1,000,000이므로 사이즈가 1,000,001인 배열을 하나 선언해서 거기에 각 값에 대한 배열 A에 포함 여부를 T/F로 저장해둔다.

그 전에 모두 음수일 수도 있으므로 배열 A를 소팅한 후 마지막 값도 음수면 따로 확인하지 않고 바로 1을 반환하도록 처리하였다. 그리고 양수인 값만 체크하면서 map에 A 배열 포함 여부를 넣어주고, 마지막으로 map을 loop 돌면서 map의 값이 false이면 그 index값을 반환하도록 처리하였다.  

public int solution(int[] A) {
    Set<Integer> foundNums = new HashSet<>();
    for (int a : A) {
        foundNums.add(a);
    }
    for (int i = 1; i <= Integer.MAX_VALUE; i++) {
        if (!foundNums.contains(i)) {
            return i;
        }
    }
    return -1;
}

다른 사람들 소스를 확인해보니 위의 코드로 훨씬 간단하게 풀었다,, Java의 컬렉션 프레임워크를 좀 더 잘 활용해봐야겠다.