[BOJ] #1764 - 듣보잡

👻 듣보잡

👉🏻 문제 보러가기 👈🏻

---

🌱 문제

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

• 시간 제한 : 2초
• 메모리 제한 : 256 MB

---

🌱 입력

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

---

🌱 출력

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

---

🌱 예제

---

🪐 입출력 1

• 입력

  3 4
  ohhenrie
  charlie
  baesangwook
  obama
  baesangwook
  ohhenrie
  clinton
  

• 출력

  2
  baesangwook
  ohhenrie
  

---

👻 풀이

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 듣보잡
    int n, m;
    cin >> n >> m;
    int sum = n + m;
    string s;
    map<string, int> names;
    while (sum--)
    {
        cin >> s;
        if (names.count(s) > 0) names[s]++;
        else names.insert({ s, 1 });
    }

    vector<string> ret;
    for (const auto &it : names)
        if (it.second > 1) ret.push_back(it.first);

    cout << ret.size() << '\n';
    sort(ret.begin(), ret.end());
    for (const auto &it : ret) cout << it << '\n';
    return 0;
}

• 시간 : 80 ms
• 메모리 : 12992 KB

---

👻 글을 마치며

나는 한 번에 입력을 전부 받은 다음 카운트를 해서 판별하는 방식을 사용했다. 다른 코드는 차례대로 진행하는 방식을 채택한 것 같다. 성능은 비슷한 것 같다. 그 중에 set을 사용한 코드가 있었는데 메모리와 시간 소요가 절반밖에 걸리지 않는 것을 확인했다. 무슨 차이인지 공부해보고 정리가 필요할 것 같다.

---

소스코드 보러가기