백준 1764 - 듣보잡 [C/C++]

1764번: 듣보잡 (acmicpc.net)

1764번: 듣보잡

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력

예제 입력 / 예제 출력

 

중복을 체크해서, 그 인원과 사전 순으로 정렬해서 사람 이름을 뱉어야 하는 문제이다.

 

중복 체크는, C에서 가장 간편한 것은 집합에 밀어 넣어 놓고 insert의 second 값이 false가 나오는지 안나오는지를 tracking 하는 것이라 개인적으로 생각한다.

 

그래서 그 알고리즘을 짜서 해결하면 될 것이라고 생각했고, 그렇게 해결 했다.

 

아래는 내가 생각한 사고 방식이다.

 

1. 우선 집합 하나를 선언한다.

 

2. 그 집합에 그냥 사람 이름을 다 밀어넣는다.

 

3. 이 때, insert(사람이름) 의 return 값의 second 값 (set.insert(무언가)의 리턴값은 pair로 나온다.

 

first는 집어넣은 원소, second는 성공 여부) 이 false라면, 이미 그 집합 안에 넣어져 있다는 것이고, 그 말은 이미 전에 등장 했다는 소리이므로, 자연스레 중복 여부가 파악된다.

 

4. 중복 여부가 파악된 사람의 이름을 vector 안에 넣어준다.

 

5. vector를 사전 순으로 정렬해서 size와 그 값들을 출력해주면 끝 !

 

아래는 그 알고리즘을 간단히 구현한 코드이다.

#include <algorithm>
#include <iostream>
#include <set>
#include <sstream>
#include <vector>

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

    string s;
    getline(cin, s);
    istringstream ss(s);
    set<string> ans;
    int a, b;
    ss >> a >> b;
    int count = 0;
    vector<string> what;
    for (int i=0;i<a+b;i++){
        string test;
        cin >> test;
        if (ans.insert(test).second == false) {
            count++;
            what.push_back(test);
        }
    }
    cout << count << '\n';
    sort(what.begin(),what.end());
    for (auto it : what) cout << it << '\n';
    return 0;
}