[LeetCode] 136. Single Number (easy)

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

Single Number - LeetCode

 

비트 연산에 관한 문제이다.

난이도는 easy.

 

짝이 주어진 배열에서 하나만 짝이 없는 수를 추출하라는 문제다.

[4, 1, 2, 1, 2]라는 배열이 있을 때, 답은 4가 된다.

 

이 문제의 포인트는

You must implement a solution with a linear runtime complexity and use only constant extra space. 이다.

해석) 선형 런타임 복잡성이 있는 솔루션을 구현하고 일정한 추가 공간만 사용해야 합니다.

 

결국 선형 시간 복잡도로 구해야 하기 때문에 O(n)이 걸리도록 해야 하며, 중첩 반복문 사용을 피해야 한다.

 

class Solution {
    //XOR 연산
    //n^0 = n
    //n^n = 0
    //두 값이 서로 같으면 0이 되고, 다르면 1이 된다.
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int n : nums) {  //4,1,2,1,2
            ret = ret ^ n;
        }
        return ret;
    }
}

 

XOR연산으로 문제를 푸는 방법은 처음 접하여, 풀이를 봐도 한동안 이해가 되지 않았다.

 

n^0 = n이고, n^n = 0 라는 식에만 집중하다 보니, 이게 비트 연산이기 때문에 비트의 성질로 접근해야 하는걸 까먹고 있었다.

 

결국에 거의 모든 풀이를 찾고 나서야, XOR의 핵심을 깨달았다.

 

풀이)

nums라는 배열엔, 짝이 있는 수와 단 하나의 짝이 없는 수가 존재한다.

 

그러므로, 배열의 수는 홀수일 것이다.

 

XOR연산의 핵심은 같은 수를 더하면 0으로 된다는 것이다.

 

(비트 연산이기 때문에 교환*결합 법칙이 성립한다.)

 

예를 들어,

 

{4, 1, 2, 1, 2} 배열의 요소들을 이진수로 변환해보자.

 

0100     -> 4
0001     -> 1
0010     -> 2
0001     -> 1
0010     -> 2

 

XOR연산은 기본적으로 비트끼리 숫자가 다르면 1 같으면 0을 반환한다.

 

위 이진수들을 하나씩 연산하게 되면, 중복되는 값이 나올 때마다 0000으로 변환 될 것이다.

 

그렇다면, 결국에 모든 배열의 요소들 돌게 됐을 때 남는 수는 4가 되고, 이것이 짝이 없는 하나의 수가 된다.