(Easy - Arrays) Leetcode - 268. Missing Number

배열에는 0부터 n까지의 숫자가 저장되어 있지만 배열의 크기는 n과 같아 0부터 n까지의 숫자 중 배열에 없는 숫자가 존재하는데 이 배열에 없는 숫자를 찾아야합니다.

 

첫번째 풀이

 

제 첫번째 풀이는 정렬을 사용했습니다. 정렬을 하면 0부터 큰 숫자대로 정렬되기 때문에 index와 value가 같게됩니다.

이때 index와 value가 다르면 그 index인 숫자가 배열에 없는 것 입니다.

int missingNumber(vector<int>& nums) {
        int n = nums.size();
        std::sort(nums.begin(), nums.end()); // 정렬
        
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) // index와 value가 다르면 index 숫자가 없는 것
                return i;
        }

        return n; // 0부터 n-1이 다 있으면 n이 없다
 }

 

두 번째 풀이

 

0부터 n까지의 숫자를 다 있는지 알아야 한다면 결국 0부터 n까지의 합이 배열에 저장된 값들의 합과 같아야 합니다.

그러므로 없는 숫자를 알기 위해서는 0부터 n까지의 합 - 배열에 저장된 값들의 합 = 배열에 없는 숫자가 됩니다.

 

int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        int sumOfarray = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            sum += i;
            sumOfarray += nums[i];
        }
        // 0부터 n까지의 합이므로 n을 더 해주고 빼기
        return (nums.size() + sum) - sumOfarray;
    }

 

이때 0부터 n까지의 숫자의 합을 한번에 계산할 수 있는 수식이 있습니다. 등차수열의 합의 공식을 사용하면 1부터 n까지 숫자의 합을 구할 수 있습니다. (0은 더해줘도 덧셈에는 영향이 없습니다.)

 

공식 : N * (N + 1) / 2

 

int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sumOfn = n * (n + 1) / 2; // 등차수열의 합 공식 (1부터 n까지의 수의 합, 0은 더해도 영향이 없다)
        for (int& i : nums)
            sumOfn -= i; // 배열에 저장된 모든 값을 빼기
            
        return sumOfn; // 남은 값은 배열에 없는 숫자와 같다.
    }