문제 푼 날짜 : 2021-09-23

문제

문제 링크 : https://www.acmicpc.net/problem/1764

접근 및 풀이

이 문제도 문자열 폭발 문제에서와 마찬가지로 find 함수를 이용하다가 시간초과가 났다.
이를 해결하기 위해서 vector가 아닌 map을 이용하였다.
듣도 못한 사람의 명단과 보도 못한 사람의 명단 입력에는 중복이 없다고 하였으니 각 명단에 존재하는 이름을 key, 명단에서 나온 횟수를 value 값하였다.
value 값이 2가 되면 듣도 보도 못한 사람으로 판단하여 출력해주었다.

코드(시간초과)

// 백준 1764번 : 듣보잡
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, M;
    vector<string> a, b, ret;
    string name = "";

    cin >> N >> M;
    while (N--) {
        cin >> name;
        a.push_back(name);
    }
    while (M--) {
        cin >> name;
        b.push_back(name);
    }
    for (string str : a) {
        if (find(b.begin(), b.end(), str) != b.end()) {
            ret.push_back(str);
        }
    }
    cout << ret.size() << '\n';
    sort(ret.begin(), ret.end());
    for (string str : ret) {
        cout << str << '\n';
    }
    return 0;
}

코드(통과)

// 백준 1764번 : 듣보잡
#include <iostream>
#include <map>

using namespace std;

int main() {
    int N, M, ans = 0;
    map<string, int> m;
    string name = "";

    cin >> N >> M;
    while (N--) {
        cin >> name;
        m[name]++;
    }
    while (M--) {
        cin >> name;
        m[name]++;
        if (m[name] >= 2) {
            ans++;
        }
    }
    cout << ans << '\n';
    for (auto it : m) {
        if (it.second >= 2) {
            cout << it.first << '\n';
        }
    }
    return 0;
}

결과

피드백

무분별한 함수 사용을 금합시다...