[Python][C++] 1764번 듣보잡

문제

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

 

 

코드

1. Python

import sys

# 입력을 빠르게 받기 위해 사용
input = sys.stdin.readline

# 듣도 못한 사람의 수 n과 보도 못한 사람의 수 m 입력
n, m = map(int, input().split())

# 듣도 못한 사람의 이름을 저장할 집합 s1
s1 = set()
# 보도 못한 사람의 이름을 저장할 집합 s2
s2 = set()

for _ in range(n):
    s1.add(input().strip())
    
for _ in range(m):
    s2.add(input().strip())

# 두 집합의 교집합을 구하고 정렬하여 리스트로 변환
s = sorted(s1 & s2)

print(len(s))
for i in s:
    print(i)

 

2. C++

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

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    int n, m;

    // 듣도 못한 사람의 수와 보도 못한 사람의 수 입력
    cin >> n >> m;

    // 문자열을 키로 사용하고 등장 횟수를 값으로 저장하는 맵
    map<string, int> mp;
    // 교집합인 이름들을 저장할 벡터
    vector<string> arr;

    // 듣도 못한 사람과 보도 못한 사람의 명단을 입력받음
    for (int i = 0; i < n + m; i++) {
        string name;

        cin >> name;

        // 이름의 등장 횟수 증가
        mp[name] += 1;
    }

    // 맵을 순회하며 등장 횟수가 2인 이름을 교집합 벡터에 추가
    for (auto pair : mp) {
        if (pair.second == 2)
            arr.emplace_back(pair.first);
    }

    cout << arr.size() << "\n";
    for (auto a : arr)
        cout << a << "\n";

    return 0;
}

 

 

풀이 

set과 map을 사용해서 해결할 수 있고, 여기서는 파이썬은 set, C++은 map으로 풀었다.

 

1. map을 사용한 방법

1. 입력 받기:
   • 듣도 못한 사람의 수 N과 보도 못한 사람의 수 M을 입력
   • 각 사람의 이름을 N + M번 입력
2. 맵에 이름 저장:
   • std::map<string, int>을 사용하여 이름을 키로, 등장 횟수를 값으로 저장
   • 이름을 입력받을 때마다 해당 이름의 등장 횟수를 1씩 증가
3. 교집합 찾기:
   • 맵을 순회하여 등장 횟수가 2인 이름을 찾습니다. 등장 횟수가 2인 경우, 듣도 못한 사람과 보도 못한 사람 명단에 모두 포함된 것
4. 결과 출력:
   • 교집합에 속하는 이름들을 사전순으로 출력

 

2. set을 사용한 방법

1. 입력 받기:
   • 듣도 못한 사람의 수 N과 보도 못한 사람의 수 M을 입력
   • N개의 이름을 std::set<string>에 저장 (듣도 못한 사람 명단)
   • M개의 이름을 또 다른 std::set<string>에 저장 (보도 못한 사람 명단)
2. 교집합 찾기:
   • 두 집합의 교집합을 구함
3. 결과 출력:
   • 교집합에 속하는 이름들을 사전순으로 출력