[백준] 10816번 숫자 카드2

문제 링크: https://www.acmicpc.net/problem/10816

문제 및 입출력

문제 접근

처음에 이진 탐색도 생각이 났고, 해쉬를 써서 하는 법도 생각이 났다. 해쉬 함수를 사용하여, O(1)의 시간으로 값을 find할 수 있다는 생각에, hash_map을 사용하여 구현하였다.
먼저 입력들을 받고, target 숫자들을 해쉬에 넣어준 후에, 상근이가 가지고 있는 값들을 해쉬에 키로 가지고 있는지 여부를 판단 후, 만약 가지고 있지 않는다면, 넘어가고 가지고 있다면, key에 대한 value를 +1해주었다.
결국 시간 복잡도는 O(N)일거 같다. 왜냐면, 해쉬 맵에서 찾는데 걸리는 시간은 O(1)이지만, N개의 값들을 찾아야되기 때문에,,

코드 구현

#include <iostream>
#include <unordered_map>

using namespace std;
int target[500001];
int sanggeon[500001];
int targetNum, haveNum;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    unordered_map<int, int> hashMap;

    cin >> haveNum;
    for(int i = 0 ; i < haveNum ; i++){
        cin >> sanggeon[i] ;
    }
    cin >> targetNum;
    for(int i = 0 ; i < targetNum ; i++){
        cin >> target[i];
        hashMap[target[i]] = 0;
    }
    for(int i = 0 ; i < haveNum ; i++){
        auto it = hashMap.find(sanggeon[i]);
        if(it != hashMap.end()){
            it->second = it->second + 1;
        }
    }
    for(int i = 0 ; i < targetNum ; i++){
        auto it = hashMap.find(target[i]);
        cout << it->second << " ";
    }
    
}

평가

오랜만에 다시 알고리즘 문제를 푸니 재미있다,,,,ㅎㅎ