Missing Number

제출코드 (에러 발생)

package leetcode;

import java.util.Arrays;

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int N = nums.length;

        int first = 0;

        for (int i = 0; i < N; i++) {
            first = nums[0];
        }

        int[] newArray = new int[N];

        for (int i = 0; i <= N; i++) { 
            newArray[i] = i; 
        }

        int answer = 0;

        for (int i = 0; i < newArray.length; i++) {
            if (nums[i] != newArray[i]) {
                answer = newArray[i];
            }
        }

        return answer;
    }
}

• 두 개의 반복문에서 ArrayIndexOutOfBoundException이 발생했다.
  왜냐하면

1. N = 3일 경우, newArray 배열의 유효한 인덱스는 0, 1, 2다. 그러나 주어진 코드는 i가 3이 될 때까지 반복하므로, newArray[3]에 접근하려 할 때 예외가 발생한다.

2. nums[i]에 접근할 때 i가 nums의 길이 이상이 되면 ArrayIndexOutOfBoundsException이 당연히 발생한다.

제출코드 (정답)

public int missingNumber(int[] nums) {
    Arrays.sort(nums);
    int N = nums.length;

    int[] newArray = new int[N + 1];

    for (int i = 0; i <= N; i++) {
        newArray[i] = i;
    }

    // nums = {3,0,1}
    // newArray = {0,1,2}

    int answer = -1; // 초기값을 변경하여 누락된 값이 없을 경우를 대비

    for (int i = 0; i <= N; i++) {
        if (i < N && nums[i] == newArray[i]) {
            continue;
        } else if (i == N || nums[i] != newArray[i]) {
            answer = newArray[i];
            break; // 누락된 숫자를 찾았으므로 반복을 중단
        }
    }

    return answer;
}

• i < N 을 i <= N으로 변경하여 에러가 발생하지 않도록 설정했다.
• 초기값을 -1로 설정하여 누락된 값이 없을 경우를 대비하였다.
• 하지만 이 방법은 실행속도가 느리다.

모범답안

import java.util.Arrays;

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        
        // Case 1
        if (nums[0] != 0) return 0;
        
        // Case 2
        if (nums[n - 1] != n) return n;
        
        // Case 3
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != i) return i;
        }
        
        return 0;
    }
}

모범답안2 (추천)

public int missingNumber(int[] nums) {
    int N = nums.length;
    int totalSum = N * (N + 1) / 2; // 총합
    int actualSum = 0;
    for (int num : nums) {
        actualSum += num;
    }
    return totalSum - actualSum; // 누락된 숫자
}

• {1,2,3,4,5}의 합을 수학적으로 표기하면 5 * (5+1) / 2다.
  즉 30/2 = 15다.

출처

https://leetcode.com/problems/missing-number/solutions/4754401/beats-98-users-4-approaches-c-java-python-javascript-explained/