[C++] 백준 1764. 듣보잡

문제 설명

들어본 적 없는 사람 목록과 본 적 없는 사람 목록을 받아 두 목록에 중복된 사람, 즉 '듣도 보도 못한 사람'을 찾는 문제이다.

접근

집합을 사용하면 사전순으로 자동 정렬된다.

두 리스트에서 중복을 찾아내는 방법은 집합이 중복을 허용하지 않는 성질을 이용했다.

 

먼저 듣도 못한 사람 목록을 집합에 저장한다. 보도 못한 사람 역시 같은 집합에 저장한다. 

이때 듣도 보도 못한 사람은 집합에 추가되지 않고, 집합의 크기가 변하지 않는다.

보도 못한 사람을 추가했을 때 집합의 크기가 달라지지 않았다면 듣도 보도 못한 사람이다. 

전체 코드

#include <iostream>
#include <set>
#include <string>

using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    int count = 0;
    set<string> no_hear;  //듣도 못한 사람 집합
    set<string> no_hear_see; //듣도 보도 못한 사람 집합

    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        string temp;
        cin >> temp;
        no_hear.insert(temp);
    }
    for (int i = 0; i < M; i++)
    {
        string temp;
        cin >> temp;
        int size = no_hear.size(); //이전 집합의 크기를 임시 저장
        no_hear.insert(temp);
        if (no_hear.size() == size)  //크기가 달라졌다면 듣도 보도 못한 사람
        {
            count++;
            no_hear_see.insert(temp);
        }
    }

    cout << count << "\n";
    for (string s:no_hear_see)
    {
        cout << s << "\n";
    }

    return 0;
}