#[C++]1764 - 듣보잡

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

1764번: 듣보잡

---

문제

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

입력

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

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

출력

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

---

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n,m;
    cin >> n >> m;
    
    vector<string> lis;
    vector<string> name;
    string l;
    
    for(int i=0; i<n; i++){
        cin >> l;
        lis.push_back(l);
    }
    sort(lis.begin(), lis.end());
    int cnt =0;
    for(int i=0; i<m; i++) {
        cin >> l;
        if (binary_search(lis.begin(), lis.end(), l)) { //이진탐색. 정렬된 상태에서만 사용
            name.push_back(l);
            cnt++;
        }
    }
    
    cout << cnt << "\n";
    sort(name.begin(), name.end());
    for(int i=0; i<name.size(); i++) {
        cout << name[i] << "\n";
    }
    return 0;
}

---

한 6-7번은 시도했다

처음엔 그냥 아무 생각 없이 for문 남발했다가 시간초과가 떠서

어쩌지 어쩌지 하다가 탐색 알고리즘 중 이진탐색을 사용해보았다.

자료구조 수업 땐 직접 구현을 다 했었는데 알고리즘 헤더파일은 참 편리하다.

*이진탐색은 정렬된 상태에서만 사용 가능하기 때문에 sort 후 사용했다.

for문을 최대한 줄이기 위해 처음 string만 벡터로 저장하고 이후의 스트링 값은 탐색키로 지정해 해당 키가 벡터에 존재하면 name벡터에 넣어주고 cnt를 카운팅한다.

처음엔 벡터 사이즈=cnt라 생각해서 그렇게 했는데 이상하게 안 되어서 그냥 cnt로 따로 카운팅 해주었다.

방금 다시 해보니 name.size()해도 값이 잘 나온다.

이상하다,, 아까 분명 안 되었는데,, 

역시 어딘가에 고발하려고 하면 잘 된다. 

 

---

수정된 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n,m;
    cin >> n >> m;
    
    vector<string> lis;
    vector<string> name;
    string l;
    
    for(int i=0; i<n; i++){
        cin >> l;
        lis.push_back(l);
    }
    sort(lis.begin(), lis.end());

    for(int i=0; i<m; i++) {
        cin >> l;
        if (binary_search(lis.begin(), lis.end(), l)) { //이진탐색. 정렬된 상태에서만 사용
            name.push_back(l);
        }
    }
    
    cout << name.size() << "\n";
    sort(name.begin(), name.end());
    for(int i=0; i<name.size(); i++) {
        cout << name[i] << "\n";
    }
    return 0;
}