백준, BOJ, 1764번 C++ [CPP]

음.. 입력과 출력이 많은 문제다.

그냥 풀자.

 

그렇다면 검색이 빠른 

BST로 구성된 자료구조를 쓰는 것이 유리하다.

오늘은 map이 그것이다.

 

사실 시간은 충분한 것 같다만

https://www.acmicpc.net/problem/1764

 

 

---

 

#맞는 풀이

#include<iostream>
#include<map>
#include<set>

using namespace std;

int N,M;
int cnt = 0;
//N과 M이 큰 숫자이기 때문에 검색이 빠르려면 map?
//또 이름이 중복이 없단다.

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    map<string, int> donthear;
    map<string, int> dontsee;
    cin >> N >> M;
    for(int i = 0; i<N; i++){
        string s;
        cin >> s;
        donthear.insert(make_pair(s, i));
    }
    
    for(int i = 0; i<M; i++){
        string s;
        cin >> s;
        dontsee.insert(make_pair(s, i));
    }
    
    //사전순 정렬이고 중복이 없으니 set이용하자
    set<string> sett;
    
    
    for (auto it=donthear.begin(); it!=donthear.end(); ++it){
        string s = it->first;
        
        auto itt = dontsee.find(s);
        //end를 return하면 존재하지 않는 것 end만 아니라면 존재함
        if(itt != dontsee.end()){
            sett.insert(s);
            cnt++;
        }
    }
    
    cout << cnt <<'\n';
    for (string s : sett){
        cout << s << '\n';
    }

}

 

그냥 중복체크 문제다.

 

첫번째이 듣지 못한 애들을 다 뒤져서

보지 못한 애들에도 있나 조사한 다음

출력하는 문제다.

 

다만 입력과 출력이 많기에 검색하기 가장 빠른 map을 썼다.