[BOJ 1764번/C++] 듣보잡

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

1764번: 듣보잡

듣보잡

문제

문제

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

 

제한사항

입력

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

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

출력

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

 

풀이

1. Map을 활용해 듣도 못한 사람들을 먼저 저장(1로 저장)을 해준다.

2. 보도 못한 사람이 듣도 못한 사람이면(즉, 수가 2이면) 듣보잡인 사람의 수를 늘리고 배열에 저장한다.

3. 배열을 정렬해서 듣보잡인 사람의 수와 사람들을 반환한다.

 

Map 말고도 Set을 이용해서도 해결할 수 있는 문제이다.

Set에 저장되었는지 아닌지를 판별해서 넣어주면 되기 때문에 큰 차이는 없다.

(나는 Map으로 풀었다.)

 

 

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

using namespace std;

string deudbojab[500000];

int main() {
    int N, M;
    map<string, int> deud;
    int count = 0;

    cin >> N >> M;

    string human = "";
    for (int i = 0; i < N; i++) {
        cin >> human;
        deud[human] = 1;
    }

    for (int i = 0; i < M; i++) {
        cin >> human;
        deud[human]++;
        if (deud[human] == 2) {
            deudbojab[count] = human;
            count++;
        }
    }

    sort(deudbojab, deudbojab + count);

    cout << count << endl;
    for (int i = 0; i < count; i++) {
        cout << deudbojab[i] << endl;
    }

    return 0;
}