[C] LeetCode 136. Single Number

문제(원문)

문제(번역)

비어있지 않은 정수 배열 nums에는 하나를 제외한 모든 요소가 정확히 2번 등장한다. 그렇지 않은 하나를 찾아라.

이 문제를 풀때 선형시간과 상수 개의 추가 공간만 사용할 수 있습니다.

 

접근 방법

처음에는 nums 만큼의 새로운 배열을 만들고 0으로 초기화해서 모든 수를 세고, count가 2가 아닌것을 찾으려고 했다.

이러면 O(n)의  시간복잡도를 갖지만, 공간복잡도가 O(n)이 되면서 문제의 제약조건을 만족하지 못한다.

 

Hint 1에는 XOR(^) 연산자의 특성을 고려하라고 나와 있다. (XOR연산자에 대해 자세한 내용은 이 글을 읽어주세요)

XOR 비트연산은 두 비트가 같으면 0, 다르면 1을 반환한다. 즉 같은 두 수에 대해서는 0을 반환한다는 것이다.

그리고 무려 교환법칙과 결합법칙이 성립한다.

 

즉 순서에 상관없이 주어진 배열의 모든 수에 대해 XOR 연산을 하게 되면,

같은 수는 교환법칙에 의해 모을 수 있고, 결합법칙으로 연산하면 0이 된다.

마지막에는 홀로 있는 수와 0을 비트 단위로 XOR하게 되므로 홀로 있는 수만 남게 된다.

 

소스 코드

int singleNumber(int* nums, int numsSize) {
    int r=nums[0];
    for(int i=1;i<numsSize;i++) r = r ^ nums[i];
    return r;
}

 

시간복잡도의 경우 배열을 순회하므로 O(N)이며, 추가적인 공간 역시 int 변수 하나만 선언하므로 O(1)이다.

문제의 제약조건에 맞게 잘 풀었다.