[LeetCode] Single Number 개인풀이

문제

integer 배열이 주어집니다. 1개의 숫자를 제외하고는 2번씩 노출됩니다. 1번만 노출되는 숫자를 찾으세요.

• 나아가기 : O(N) 시간복잡도와 O(1)의 공간복잡도를 가질 수 있도록 해결할 수 있으면 좋습니다.

예제 1
입력 : [2,2,1]
출력 : 1

예제 2
입력 : [4,1,2,1,2]
출력 : 4

예제 3
입력 : [1]
출력 : 1

제약 조건

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• 각 원소는 1개의 숫자를 제외하고 2번씩 노출
• 문제 원문 : https://leetcode.com/problems/single-number

개인 풀이

주어진 문제의 심화부분에 시간복잡도 O(N), 그리고 공간 복잡도 O(1)로 해결할 수 있다면 좋다는 것을 보고 만족할 수 있도록 어떻게 할 수 있을까 고민을 해보았습니다. 개인적인 생각으로 2가지 정도로 보았습니다. 첫번째는 순차적으로 swap을 하면서 테이블의 변화를 주는 것과 두번째는 bit 컨트롤이었습니다. 하지만 아쉽게도 제가 생각한 방법으로는 해결하지 못하였습니다.

아래는 시간 복잡도 O(N), 공간 복잡도 O(N)으로 해결한 방법입니다. HashMap을 이용하였고 Key에따라 counting을 해주는 단순한 방법으로 해결하였습니다. 그리고 마지막에 hashMap을 순회하며 counting이 1인값을 return 해주는 방식을 사용했습니다.

코드

public int singleNumber_3(int[] nums) {
    HashMap<Integer, Integer> hashMap = new HashMap<>();

    for (int index : nums) {
        Integer integer = hashMap.getOrDefault(index, 0);
        hashMap.put(index, integer + 1);
    }

    for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }

    return -1;
}

최적화 풀이

운이 좋게도 해당문제는 Solution 페이지가 열려 있었으며 시간 복잡도 O(N), 공간 복잡도 O(1)로 해결할 수 있는 최적화 코드를 쉽게 찾을 수 있었습니다. 그것은 바로 XOR 연산을 하는 것입니다.

XOR 연산에 대해서 잠시 알아보겠습니다. XOR는 배타적 논리합이라고 하는데요. bit 컨트롤할때 주로 사용되며 아래와 같은 조건을 만족합니다.

• a와 0의 베타적 논리합은 a 입니다.
  • a ⊕ 0 = a
• a와 a의 베타적 논리합은 0 입니다.
  • a ⊕ a = 0
• 연산간의 이동과 묶음이 자유롭습니다.
  • a ⊕ b ⊕ a = ( a ⊕ a ) ⊕ b = 0 ⊕ b = b

코드

베타적 논리합을 기본으로하여 코딩하면 아래와 같습니다.

public int singleNumber(int[] nums) { // xor를 이용
    int temp = 0;
    for (int index = 0; index < nums.length; index++) {
        temp ^= nums[index];
    }
    return temp;
}

마무리

오늘은 이렇게 Single Number 문제를 풀어보았습니다.

감사합니다.