Single Number III (LeetCode)

(출처) https://leetcode.com/problems/single-number-iii/

개요

int배열이 인풋으로 주어질 때, 배열의 int 요소 중 중복 없이 단 1번만 등장하는 요소를 찾아서 리턴해주면 되는 문제.

들어오는 인풋배열의 길이는 최대 3만이므로 O(N)의 시간복잡도면 충분히 해결할 수 있어 보였다.

처음에는 단순하게 정수 0부터 9까지를 표현하는 길이가 10인 배열을 만든 다음, 주어진 인풋배열의 int 요소들을 하나씩 탐색해 가면서 각 요소들의 등장횟수를 일일이 카운팅하면 쉽게 문제를 해결할 수 있겠다고 생각했다.

그런데 문제의 조건을 보니 int요소는 0~9까지의 정수가 아니라 -2^31 ~ 2^31 범위의 정수...😅

따라서 존재하는 모든 범위의 정수 카운팅 배열을 미리 준비하는 식으로 문제를 푸는 건 사실상 불가능해 보였고, hashTable을 이용해서 요소가 등장할 때마다 그때그때 카운팅 해나가는 식으로 접근해야 할 것 같았다.

hashTable을 이용한 풀이

풀이법은 간단했다. 주어진 인풋배열을 for문 돌려서 처음부터 끝까지 순회한다. 순회하면서 마주치는 각 int요소를 key로 하고, 등장횟수를 value로 하여 hashTable을 작성해 나간다.

등장횟수를 전부 카운팅하여 기록하는 작업이 끝났다면, 다시 한번 인풋배열을 for문으로 순회하면서 이번에는 hashTable과 맵핑하여 등장횟수를 체킹해준다.

등장횟수(value값)가 만약 1이라면 result에 추가하고 아니면 패스하는 식으로.

이후 result를 최종적으로 return 해주었다.

코드

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int,int> um;
        vector<int> result;
        for(int i : nums) {
            if(um.find(i) == um.end()) um[i] = 1;
            else {
                um[i]++;
            }
        }

        for(int i : nums) {
            if(um[i] == 1) result.push_back(i);
        }

        return result;
    }
};

int main() {
    Solution *solution = new Solution();
    vector<int> nums = {1,2,1,3,2,5};
    solution->singleNumber(nums);
    return -1;
}