[LeetCode/easy] Single Number (C++)

leetcode.com/problems/single-number/

 

먼저 hash를 이용한 풀이입니다. unordered_map을 선언하여 key는 수, value는 빈도 수를 저장합니다. iterator로 map을 탐색하면서 value 값이 1인 key를 리턴하면 해결할 수 있습니다.

 

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> um;
        for(auto n : nums) {
            um[n]++;
        }

        for(auto it = um.begin(); it != um.end(); it++) {
            if(it -> second == 1) {
                return it -> first;
            }
        }
        
        return 0;
    }
};

 

다음은 bit 연산을 이용한 풀이입니다. XOR 연산을 사용하는데, 해당 연산은 양쪽 비트가 서로 다르면 1, 같으면 0을 리턴합니다. 다음 예시를 확인해봅시다.

 

A^0 = A

A^A = 0

A^B^A = (A^A)^B = 0^B = B

 

이를 이용하면 문제의 조건에서 수 하나를 제외하곤 모두 두번씩 나온다고 했으므로, 한번 나온 수를 제외하고 나머지는 전부 짝지어져 0을 리턴하게 될 것입니다. 그 수와 0을 XOR 연산하면 자신을 리턴하므로 쉽게 문제를 해결할 수 있습니다.

 

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