[LeetCode] 268. Missing Number

LeetCode - 268. Missing Number 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/missing-number/

풀이

nums에는 0부터 nums.size()까지의 숫자로 구성되어 있고 중복되는 숫자는 존재하지 않지만 숫자 하나가 누락되어 있다. 이 경우 누락된 숫자를 반환하는 문제이다.

우선 nums의 길이가 N이라고 했을 때 nums가 가질 수 있는 원소의 범위는 [0, N]이므로 bool chk[10001] 배열을 선언하고 N개만큼 false로 초기화한다.

이후, nums의 원소를 의미하는 elem 변수를 인덱스로 하여 chk[elem] = true를 수행하고, 이 과정이 끝난 후 [0, N)만큼 반복하면서 chk[i]가 false인 위치를 찾을 때 i를 반환한다.

만약 이 과정에서 반환되지 못하면 N값이 누락된 것이기 때문에 N을 반환한다.

소스 코드

class Solution {
    bool chk[10001];
public:
    int missingNumber(vector<int>& nums) {
        const int N = (int)nums.size();
        fill(chk, chk + N, false);
        for (int elem : nums) {
            chk[elem] = true;
        }
        for (int i = 0; i != N; ++i) {
            if (!chk[i]) {
                return i;
            }
        }
        return N;
    }
};