[LeetCode] 268. Missing Number (C++)

문제

 

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

Missing Number - LeetCode

 

풀이

 

난이도: Easy

 

난이도 순으로 3가지 풀이를 소개하겠다.

(가장 중요한 풀이는 3번째라고 생각한다.)

 

1. 정렬 time complex O(n log n)

가장 쉬운 풀이는 배열을 정렬하고 순서대로 살펴보며 빠진 수를 찾는 것이다.

하지만 배열의 정렬에 큰 복잡도가 소요된다.

 

 

2. 전체 합 이용 time complex O(n) using extra O(1) space

배열에는 0~n까지의 수들을 중복 없이 가지고 있다.(빠진 수 제외)

따라서 0~n까지의 수를 모두 더한 전체 합에서 배열의 수들을 하나씩 빼주면 결과적으로 빠진 수가 계산된다.

 

 

 

3. 비트 연산자 XOR time complex O(n) using extra O(1) space

시간 복잡도 자체는 2번과 동일하지만 비트 연산자를 이용하기 때문에 사실 훨씬 빠르게 동작한다.

여기서 중요한것이 XOR의 commutative(가환성)와 associative(결합성) 성질이다.

간단히 말하면 계산식의 순서를 바꾸어 계산하더라도 동일한 결과가 나온다는 것이다.

 

XOR은 같은 값이 두 번 적용되면 결국 초기 값으로 돌아오는데, 이를 위의 성질과 연결시키면 순서가 다르더라도 같은 값만 두 번씩 XOR 연산되면 결국 초기값에서 변하지 않는다는 것이다.

 

우리가 찾고 싶은 값은 0~n 중에 배열에서 제외된 수이기 때문에 0~n의 값을 초기 값 0에 모두 XOR 하고,

배열의 모든 수를 다시 XOR 하면 제외된 수만이 한 번만 XOR 되어 값에 남아있게 된다.

이러한 연산은 한 번의 for문만으로 구현 가능하기 때문에 O(n)의 시간 복잡도를 가진다.

 

풀이 참조: https://leetcode.com/problems/missing-number/discuss/69777/C%2B%2B-solution-using-bit-manipulation

C++ solution using bit manipulation - LeetCode Discuss