Table of contents

코딜리티 PermMissingElem

길이가 N, 요소가 [1..(N + 1)] 의 숫자로 채워져있는 배열에서 빠진 숫자를 찾는 문제이다.

첫번째 풀이

private int findMissingNumber(int[] A) {
    Arrays.sort(A);
    for (int i = 0; i < A.length; i++) {
        if (i + 1 != A[i]) return i + 1;
    }
    return 0;
}

배열을 정렬 한 뒤 n과 n의 인덱스 i를 비교하여 i번째 요소에 i + 1의 값이 들어있지 않다면 i + 1이 빠진 숫자라고 판단했다. [2, 1, 3, 5]의 경우 [1, 2, 3, 5]로 정렬되며, 3번째 요소의 값이 4가 아니기 때문에 4를 반환한다.

결과는 50점이 나왔다. 배열의 사이즈가 1, 2인 경우와 100,000인 경우의 테스트 케이스를 통과하지 못한다. [1]의 경우 N이 1이므로 [1, 2]에서 2가 빠진 요소이므로 2가 반환되어야 한다. 마찬가지로 [2]의 경우 1이 반환되어야 한다. [1, 2]의 경우 N이 2이므로 [1, 2, 3]에서 3이 빠진 요소이므로 3이 반환되어야 한다.

  1. [1]
    1. (0 + 1) == 1 이므로 빠진 요소가 없다고 판단하여 0 반환 (오답)
  2. [1, 2]
    1. (0 + 1) == 1, (1 + 1) == 2 이므로 빠진 요소가 없다고 판단하여 0 반환 (오답)

두번째 풀이 (SUM)

private int findMissingNumber3(int[] A) {
    long sum = sumStartOneTo(A.length + 1);
    for (int i = 0; i < A.length; i++) {
        sum -= A[i];
    }
    return (int) sum;
}

private long sumStartOneTo(int n) {
    return ((long) n * (n + 1)) / 2;
}

1부터 N까지의 합계 (N * (N + 1)) / 2를 구하여 배열의 모든 값을 뺀다. 결과로 0이 아닌 숫자가 나왔다면 해당 숫자가 빠진 숫자이다. 주의해야할 부분은 형변환이다. 배열의 사이즈 N이 큰 값인 경우 합계를 구하는 과정에서 Integer 범위를 초과한다. 해결법은 보다 더 큰 범위를 가진 long을 이용하여 마지막 결과값만 int로 반환하면 된다.

정리

문제를 정확하게 이해해야 한다는 것을 깨달았다. 특히 입력값의 크기에 따라 변환되는 숫자의 범위를 주의해야 한다. 이는 문제에서 주어진 가정을 정확하게 이해하지 않으면 놓치기 쉬운 부분이다. 실제 기업 테스트를 볼 때는 한번 제출하면 수정할 수 없을 것 이기 때문에, 제출하기 전에 여러 테스트 케이스를 집어넣고 확인해보는게 좋을 것 같다. 배열의 경우 빈 배열, 최대 사이즈의 배열, 요소가 한 개, 두 개 만 있는 배열은 필수로 테스트하고 기본 자료형의 경우 최소값, 최대값, 범위에 맞지 않는 값까지 테스트하도록 노력해야겠다.