[백준 1764] 듣보잡

백준 1764번 - 듣보잡

백준 1764번

❓ 문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 
이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 
이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. 
N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.

예제 입력1
3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력1
2
baesangwook
ohhenrie

---

✏️ 풀이

처음엔 vector find로 해결하려 하였으나, TLE가 났다.
input N과 M이 500,000까지 들어올 수 있다는 것을 보지 못했었고, 더 깔끔한 코드가 필요했다.
아래는 처음 vector find를 이용한 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> no_listen;
vector<string> result;

int N, M;

int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> N >> M;

  for (int i=0; i<N; i++) {
    string temp;
    cin >> temp;
    no_listen.push_back(temp);
  }

  for (int i=0; i<M; i++) {
    string temp;
    cin >> temp;
    auto it = find(no_listen.begin(), no_listen.end(), temp);
    if (it != no_listen.end())
      result.push_back(temp);
  }

  sort(result.begin(), result.end());
  cout << result.size() << "\n";
  for (auto it=result.begin(); it!=result.end(); it++) {
    cout << *it << "\n";    
  }
  
  return 0;
}

듣도 못한 사람을 입력받고, 보도 못한 사람을 입력 받으면서 바로 find를 수행했다.
하지만 시간초과가 났고, 시간을 더 절약할 필요가 있었다.
find에 대한 부분을 어떻게 해결할까 생각하다 map을 떠올렸고 위 로직에서 vector를 map으로 바꾸고 find 부분만 map으로 바꾸기로 했다.

결과는 성공이었다.
vector에서 find함수는 모든 index를 다 검사하는 반면, map의 find는 tree 구조이기 때문에, 더 빠르다는 것을 알게 되었다.

또한, vector에서 find함수는 시간복잡도가 O(N)이고, map에서 find는 시간복잡도가 O(logN)라는 것과 vector를 이용한 find보다 map의 find가 더 빠르다는 것을 기억하도록 하자!

---

✔️ 정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

map<string, bool> no_listen;
vector<string> result;

int N, M;

int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> N >> M;

  for (int i=0; i<N; i++) {
    string temp;
    cin >> temp;
    no_listen.insert({temp, true});
  }

  for (int i=0; i<M; i++) {
    string temp;
    cin >> temp;
    auto it = no_listen.find(temp);
    if (it != no_listen.end())
      result.push_back(temp);
  }

  sort(result.begin(), result.end());
  cout << result.size() << "\n";
  for (auto it=result.begin(); it!=result.end(); it++) {
    cout << *it << "\n";    
  }
  
  return 0;
}