리트코드 - 136. Single Number

리트코드 - 136. Single Number

출처 - https://leetcode.com/problems/single-number/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 비어 있지 않은 정수 배열 `nums`에서, 하나를 제외한 모든 요소는 두 번씩 나타납니다. 그 '하나'를 찾아야 합니다. 선형 시간 복잡도를 가진 해결책을 구현하고 상수의 추가 공간만 사용해야 합니다.

 

의사코드

answer = 0 반복문 시작 (배열 순회)     answer = 배열값을 XOR연산 반복문 종료 answer 리턴

 

풀이코드

class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;
        for (int num : nums) {
            answer ^= num;
        }

        return answer;
    }
}

 

코드설명

답이 정해져 있고 XOR연산에 대해 꼭 알아두어야 하는 문제이다.

문제에서 선형시간 동안 풀어야 하고 공간복잡도 또한 O(1)을 요구하고 있으므로, 변수 하나로 풀어야만 한다.

따라서 자바에서도 XOR 연산을 하는 연산자를 사용해서 풀어야 한다.

 

XOR 연산은 둘 중 하나만 1일 때 1을 리턴한다.

이 연산의 특징으로는 교환법칙과 결합법칙도 성립하기 때문에 배열에도 사용할 수 있다.

0 XOR x = x가 되고, x XOR x = 0이 되면서 교환법칙이 성립되므로 순서에 상관이 없다.

 

따라서 어떠한 배열 없이 변수하나만으로 값을 넣었다가 뺼 수 있게 된다.

 

예를 들어서 [2,3,4,2,3] 이라는 배열이 있다고 하자.

각 배열을 이진수로 간단히 표현하면

2 = 010

3 = 011

4 = 100

이 된다.

 

맨 처음 배열부터 확인하는데 먼저 answer가 0이므로 XOR 연산을 하면 answer = 010 된다.

다음으로 010과 011(3)을 연산하면 001이 된다.

다음으로 011과 100(4)을 연산하면 101이 되고, 다시 이를 010(2)과 연산하면 111이 된다.

마지막으로 111과 011을 연산하면 100이 된다.

 

answer의 결과로 짝이 없는 4가 나오는 것이다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

이전 문제들이 비트 연산자에 대한 부분이라 아무리 생각해도 이 문제도 그렇게 풀어야 하는 것 같았다.

값의 순서와 상관없이 넣었다가 빼면 좋을것 같다는 생각을 했는데 자료구조를 사용하지 않고 어떻게 할 수 있을지 생각해보다가 XOR가 있다는 걸 떠올렸다.

 

적용했더니 바로 답이 나와서 다했이었다. 비트에 대한 공부가 더 필요할 거 같긴 하다.

 

정리

XOR연산으로 배열에서 유일한 값을 찾는 방법