[ leetcode 문제풀이 ] Missing Number

https://leetcode.com/problems/missing-number/

Missing Number - LeetCode

(Missing Number 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

< Missing Number 문제 설명 >

 

Missing Number 문제는 다음과 같다.

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

0에서 n사이의 서로 다른 n개의 정수를 갖는 배열 nums에 대해 범위 내에서 nums에 빠진 유일한 숫자를 리턴하여라.

 

다음 세 가지 출력 예시가 주어졌다.

 

주어진 제한 조건은 n은 배열 nums의 길이, 1 ≤ n ≤ 10^4, 0 ≤ nums[i] ≤ n 이며 nums는 중복된 값을 갖지 않는다는 것이다. Follow up question으로는 O(1)의 추가 공간복잡도와 O(n) 시간복잡도만을 사용해 솔루션을 구현할 수 있겠는가? 이다.

 

 

---

< Missing Number 문제 접근 - 기본 >

 

0 부터 n까지의 숫자가 무작위 순서로 배열되어 있을 때, 그 합이 n(n+1)/2 가 된다. 이 사실을 적용해 n(n+1)/2와 주어진 배열의 전체 원소의 합 간의 차를 구함으로써 missing number을 구할 수 있다. 이를 코드로 나타내면 다음과 같다. (Cpp 사용)

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    int total = n*(n+1)/2;
    int sum = 0;
    for(int i=0;i<n;i++){
    	sum += nums[i];
    }
    return total - sum;
}

이 코드의 시간복잡도는 for문에 의해 결정되며 상수 시간 연산을 n회 반복하므로 O(n)임을 알 수 있고, 추가 공간복잡도는 새로 선언한 정수 n, total, sum, i에 의해 나타나며 이는 32바이트의 상수 공간이기에 O(1)의 추가 공간복잡도를 갖는다.

 

 

---

< Missing Number 문제 접근 - 심화 >

 

위에서는 배열의 원소 전체에 대해 덧셈 연산을 통해 missing number을 구하였다. 

그렇다면 덧셈 연산이 아닌 bitwise operation을 사용해서 비슷한 아이디어를 적용할 수는 없을까 하는 생각에 덧셈 연산을 XOR 연산으로 대체해 알고리즘을 구성하였다. 그 원리는 다음과 같다.

 

XOR 연산은 다음 두 성질을 만족한다.

• A ⊕ B = B ⊕ A                       (교환 법칙)
• (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)      (결합 법칙)

따라서, 덧셈과 마찬가지로 원소의 배열 순서와 관계 없이 전체 원소에 대한 XOR 값은 항상 같은 값을 나타낸다.

한편, A ⊕ A = 0 이므로 배열 내의 모든 원소에 대한 XOR 값과 0 ~ n에 대한 XOR 값을 XOR 해주면 구하고자 하는 missing number이 나오게 된다.

 

runtime 측면에서의 이점을 가져오고자 0 ~ n에 대한 XOR 값의 패턴을 계산해주었다.

그 결과, n mod 4 = 0인 경우 n / n mod 4 = 1인 경우 1 / n mod 4 = 2인 경우 n+1 / n mod 4 = 3인 경우 0

을 0 ~ n에 대한 XOR 값으로 가짐을 확인할 수 있었다. 

 

이 사실들을 바탕으로 작성한 코드는 아래와 같다. (Cpp 사용)

int missingNumber(vector<int>& nums) {
    int missing_xor = 0;
    int n = nums.size();
    for(int i=0;i<n;i++){
        missing_xor = missing_xor^nums[i];		// nums 원소에 대한 xor 계산
    }
        
    int correct_xor;
    switch(n % 4){					// 0 ~ n에 대한 xor 값 대입
        case 0:
            correct_xor = n; break;
        case 1:
            correct_xor = 1; break;
        case 2:
            correct_xor = n+1; break;
        case 3:
            correct_xor = 0; break;
    }
        
    return missing_xor^correct_xor;	
}

이 코드의 시간복잡도는 O(n)이고, 추가 공간복잡도는 O(1)을 만족한다. 한편, bitwise operation으로 연산이 구성되었기에 덧셈을 이용한 알고리즘보다 시간적으로 유리하다.