ksh021144

ksh021144

Learn more, Do more.

[LeetCode] 136. Single Number

1 분 소요

LeetCode - 136. Single Number 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/single-number/

풀이

비어 있지 않은 정수 벡터가 주어지고, 배열의 원소는 단 하나를 제외하고 두 번씩 나타난다.

이때 하나만 나타나는 원소의 값을 반환한다.

해시를 사용하여 접근하기

이 문제를 해결하기 위해 해시 자료구조를 사용하는 것을 생각해볼 수 있다.

벡터의 원소를 key로 하여 해당 key가 몇 번 등장했는지 빈도 수를 증가시킨다.

하나의 원소를 제외한 모든 원소는 두 번씩 나타나므로 빈도수가 2가 되면 제거한다.

이것을 반복했을 때 가장 마지막에 남아있는 원소가 한 번만 등장한 원소가 된다.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> um;
        for (int k : nums) {
            ++um[k];
            if (um[k] == 2) { // check 2
                um.erase(k);
            }
        }
        return um.begin()->first;
    }
};

비트 연산을 통해 접근하기

모든 원소가 두 번씩 등장한다는 조건에 의해 XOR 연산을 생각할 수 있다.

XOR 연산의 특징은 다음과 같다.

  • 0으로 초기화 되어있는 임의의 변수 ret 에 어떤 값 k를 두 번 XOR 연산하면 ret 의 결과는 항상 0이다.
  • 0으로 초기화 되어있는 임의의 변수 ret 에 어떤 값 k를 한 번 XOR 연산하면 ret 의 결과는 항상 k이다.
ret = 0;
ret ^= k;
// ret is alwyas k.
ret ^= k;
// ret is always 0 (zero).

따라서 이 문제는 문제 조건(단 하나의 숫자를 제외한 모든 수는 두 번 등장한다)에 의해 XOR연산을 활용하여 풀 수 있다. (소스 코드는 아래에)

소스 코드

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int k : nums) {
            ret ^= k;
        }
        return ret;
    }
};

참고