백준 1764번 [듣보잡](C++) -yes6686- 티스토리

백준 문제 풀이: 1764 [듣보잡]

---

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

문제 설명:

듣도 못한 사람의 명단과 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 출력하세요. 이 명단은 사전순으로 정렬해야 합니다.

입력 조건:

• 첫 번째 줄에 듣도 못한 사람의 수 N과 보도 못한 사람의 수 M이 주어집니다. (1 ≤ N, M ≤ 500,000)
• 다음 N개의 줄에는 듣도 못한 사람의 이름이 주어집니다.
• 다음 M개의 줄에는 보도 못한 사람의 이름이 주어집니다.

출력 조건:

• 듣도 보도 못한 사람의 수와 명단을 사전순으로 한 줄에 하나씩 출력합니다.

---

문제 해결 코드

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

map<string, int> m;
vector v;

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

    int n, mCount;
    cin >> n >> mCount;

    string name;
    for (int i = 0; i < n; i++) {
        cin >> name;
        m[name] = 1; // 듣도 못한 사람 저장
    }

    for (int i = 0; i < mCount; i++) {
        cin >> name;
        if (m[name] == 1) { // 보도 못한 사람도 듣도 못한 사람에 포함되면 추가
            v.push_back(name);
        }
    }

    // 사전순 정렬
    sort(v.begin(), v.end());

    // 결과 출력
    cout << v.size() << '\n';
    for (const string& s : v) {
        cout << s << '\n';
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 `map`을 사용하여 듣도 못한 사람의 명단을 저장하고, 보도 못한 사람의 명단을 비교하여 중복되는 이름을 찾습니다.

• 입력 처리:
  • `map`에 듣도 못한 사람의 이름을 저장합니다.
  • 보도 못한 사람의 이름을 읽으며 `map`에서 중복 여부를 확인합니다.
• 결과 처리:
  • 중복된 이름을 `vector`에 저장하고, 이를 사전순으로 정렬합니다.
  • 정렬된 결과를 출력합니다.

시간 복잡도 분석:

• 입력 처리: O(N + M), 각각 듣도 못한 사람과 보도 못한 사람 입력.
• 정렬: O(K log K), K는 중복된 이름의 개수.
• 전체 시간 복잡도: O(N + M + K log K).

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
5 5
Jimin
Yoongi
Namjoon
Hoseok
Jin
Jimin
Tae
Yoongi
Jin
Jungkook

출력:
3
Jimin
Jin
Yoongi

듣도 보도 못한 사람의 명단이 사전순으로 정렬되어 정확히 출력됩니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!