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

1. 문제

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

2. 입력

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

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

3. 출력

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

4. 풀이

STL의 set 라이브러리와 algorithm의 set_intersection 함수를 사용하여 교집합을 찾아내는 방식으로 풀이함

5. 소스코드

1. 첫번째 시도

      

      

      

    
    

      <code />
    
string getName() {
    string name;
    cin >> name;
    return name;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<string> names;
    vector<string> overlap;
    int n, m;
    int cnt = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        names.push_back(getName());
    }
    sort(names.begin(), names.end());
    for (int i = 0; i < m; i++) {
        string name = getName();
        auto it = find(names.begin(), names.end(), name);
        if (it != names.end()) {
            cnt++;
            overlap.push_back(name);
        }
    }
    cout << cnt << '\n';
    for (int i = 0; i < overlap.size(); i++) {
        cout << overlap[i] << '\n';
    }
    return 0;
}

코드 작성할 때부터 이건 아닌 것 같다 생각들었는데 그냥 제출해보니까 역시 시간 초과;;
그래서 stl중 algorithm 에 있는 교집합 함수와 set을 사용해서 다시 한번 시도함
2. 두번째 시도

      

      

      

    
    

      <code />
    
string getName() {
    string name;
    cin >> name;
    return name;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    set<string> a;
    set<string> b;
    int n, m;
    int cnt = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        a.insert(getName());
    }

    for (int i = 0; i < m; i++) {
        b.insert(getName());
    }
    set<string> c;
    set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(c, c.begin()));
    cout << c.size() << '\n';
    for (set<string>::iterator it = c.begin(); it != c.end(); it++) {
        cout << *it << '\n';
    }
    return 0;
}

통과~(다른 사람꺼 보고나서 깨달았지만 그냥 벡터 쓰고 이진탐색이라는 좋은 방법이 있었당..)