[백준,c++] 10546번 - 배부른 마라토너

문제

10546번: 배부른 마라토너

 

코드

#include <iostream>
#include <unordered_map>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    string name;
    unordered_map<string,int> umap;
    for(int i=0; i<N; i++){
        cin>>name;
        umap[name]++;
    }
    for(int i=0; i<N-1; i++){
        cin>>name;
        umap[name]--;
    }
    for(auto it = umap.begin(); it!=umap.end(); it++){
        if(it->second!=0) cout<<it->first<<'\n';
    }
}

 

풀이

단순 map 자료구조만 활용하면 쉽게 해결할 수 있습니다. 

C++에서 map은 레드 블랙트리로 구현되어 있습니다.  자동으로 키값을 기준으로 정렬이 된다는 장점이 있지만 시간 복잡도는 O(logN)입니다.

따라서 O(1) 시간복잡도를 가지는 hashmap을 사용하면 더 빠른데, C++에서 hashmap은 unorderd_map으로 선언이 가능합니다.