[Codility] PermMissingElem

분석

문제는 워낙 간단하고 쉽다. 단 해당 문제의 Lesson 주제가 Time Complexity인 만큼 시간 복잡도를 최소화하는 것이 문제의 의도로 보인다. 

가장 쉽게 떠올릴 수 있는 방법은 N개의 크기 배열 A를 받았을 때 (1부터 N+1)까지의 숫자를 전부 Hash의 Key로 넣고 하나씩 Remove 하는 것이다. 이렇게 하면 가장 마지막에 남는 Key가 답이 된다. 하지만 이 방법은 Hash에 넣는데 N+1번, 그리고 A배열을 순회하며 찾는데 N번 걸리므로 O(n^2)이다. 

O(N)으로 끝낼 수 있는 방법은 배열을 딱 한 번만 순회하는 것이다. 처음 A 배열을 받으면 1~N+1 숫자의 합을 구한다. 그리고 A 배열을 순회하면서 합에서 값을 한 개씩 뺀다. 이렇게 하면 없는 숫자는 뺄 수 없으므로 최종 남는 숫자가 답이 된다.

Code

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

        if (A.length == 0) {
            return 1;
        }

        double n = ((double) (1 + (A.length + 1)) / 2 * (A.length+1));

        for (int a : A) {
            n -= a;
        }

        return (int) n;
    }
}