Easy is Perfect

[백준] 1764번 C/C++ 풀이 _ 듣보잡

  • melonicedlatte
  • Dec 01, 2018


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

듣보잡 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB83493256228540.088%

문제

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

입력

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

출력

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

예제 입력 1 

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1 

2
baesangwook
ohhenrie

출처

알고리즘 분류

풀이

저는 set을 이용하여 문제를 해결했습니다.
c++의 set은 자동으로 정렬되는 성질이 있습니다. 

dont_see set에 못본얘들을 전부 넣었습니다.
dont_hear set에는 못들은얘들을 전부 넣었습니다.

그리고 iterator 를 하나씩 이동하면서 두 set에서의 string을 비교하였습니다. (정렬된 두 set을 하나하나씩 비교)
만약, 한 set에서의 string 이 더 작다면 다음으로 넘어가고, 두 set의 string이 같으면 답에 추가해주었습니다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string> 
#include <set>
using namespace std;
int main() { 
    int N, M; cin >> N >> M;
    set<string> dont_see, dont_hear, dont_two;
    for (int idx = 0; idx < N; idx++) {
        string sub; cin >> sub; 
        dont_see.insert(sub);
    }
    for (int idx = 0; idx < M; idx++) {
        string sub; cin >> sub;
        dont_hear.insert(sub);
    }
    auto see_one = dont_see.begin();
    auto hear_one = dont_hear.begin();
    for (; see_one != dont_see.end();) {
        // 다 탐색하면 종료 
        if (hear_one == dont_hear.end()) break;
        // 순서 비교
        if (*hear_one > *see_one)
            see_one++;
        else if (*hear_one < *see_one) 
            hear_one++;
        else {
            dont_two.insert(*see_one);
            hear_one++;
            see_one++;
        } 
    }
    cout << dont_two.size() << "\n";
    for (auto each : dont_two) 
        cout << each << "\n";
    return 0;
}
cs



Search