BOJ 1764: 듣보잡

Note

Set을 이용한 교집합 찾기 기법을 활용하여 해결하는 문제입니다.

---

문제

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

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

입력

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

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

출력

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

예제

예제 입력 1:

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1:

2
baesangwook
ohhenrie

---

문제 분석

이 문제는 두 집합의 교집합을 찾는 문제입니다. 듣도 못한 사람과 보도 못한 사람 중 겹치는 사람을 찾아야 합니다.

핵심 포인트

1. 교집합 찾기: 듣도 못한 사람 명단과 보도 못한 사람 명단의 공통 원소
2. 사전순 정렬: 결과를 사전순으로 정렬하여 출력
3. 효율성: N, M이 최대 500,000이므로 효율적인 자료구조 사용 필요

---

해결 방법

Set을 이용한 교집합 찾기 기법을 사용합니다:

1. 듣도 못한 사람 명단을 Set으로 변환
2. 보도 못한 사람 명단을 순회하며 Set에 있는지 확인
3. 교집합을 사전순으로 정렬하여 출력

---

코드 구현

제공된 코드

import sys
 
no_heard = set([])
no_heard_and_seen: list[str] = [] # 듣보잡
 
readline = sys.stdin.readline
 
n, m = map(int, readline().rstrip().split())
 
for _ in range(n):
    name = readline().rstrip()
    no_heard.add(name)
 
for _ in range(m):
    name = readline().rstrip()
 
    if name in no_heard:
        no_heard_and_seen.append(name)
 
print(len(no_heard_and_seen))
 
no_heard_and_seen.sort()
 
for name in no_heard_and_seen:
    print(name)

코드 분석

1. 입력 처리

import sys
 
readline = sys.stdin.readline
 
n, m = map(int, readline().rstrip().split())

• 입력 최적화를 위해 sys.stdin.readline() 사용
• 듣도 못한 사람 수 N과 보도 못한 사람 수 M을 입력받음

2. 듣도 못한 사람 명단을 Set으로 저장

no_heard = set([])
 
for _ in range(n):
    name = readline().rstrip()
    no_heard.add(name)

• Set 자료구조를 사용하여 O(1) 시간에 조회 가능
• 듣도 못한 사람의 이름을 Set에 추가

3. 보도 못한 사람 명단에서 교집합 찾기

no_heard_and_seen: list[str] = []
 
for _ in range(m):
    name = readline().rstrip()
    
    if name in no_heard:
        no_heard_and_seen.append(name)

• 보도 못한 사람의 이름을 하나씩 확인
• name in no_heard: Set의 in 연산은 O(1) 시간
• 교집합에 속하는 이름을 리스트에 추가

4. 결과 출력

print(len(no_heard_and_seen))
 
no_heard_and_seen.sort()
 
for name in no_heard_and_seen:
    print(name)

• 듣보잡의 수를 먼저 출력
• 사전순으로 정렬
• 각 이름을 한 줄씩 출력

개선된 코드

더 Pythonic하게 작성한다면:

import sys
 
readline = sys.stdin.readline
 
n, m = map(int, readline().rstrip().split())
 
# 듣도 못한 사람 명단을 Set으로 저장
no_heard = set()
for _ in range(n):
    no_heard.add(readline().rstrip())
 
# 보도 못한 사람 명단에서 교집합 찾기
no_heard_and_seen = []
for _ in range(m):
    name = readline().rstrip()
    if name in no_heard:
        no_heard_and_seen.append(name)
 
# 결과 출력
print(len(no_heard_and_seen))
no_heard_and_seen.sort()
for name in no_heard_and_seen:
    print(name)

또는 리스트 컴프리헨션을 사용:

import sys
 
readline = sys.stdin.readline
 
n, m = map(int, readline().rstrip().split())
 
# 듣도 못한 사람 명단을 Set으로 저장
no_heard = {readline().rstrip() for _ in range(n)}
 
# 보도 못한 사람 명단에서 교집합 찾기
no_heard_and_seen = [readline().rstrip() for _ in range(m) 
                     if readline().rstrip() in no_heard]
 
# 결과 출력
print(len(no_heard_and_seen))
no_heard_and_seen.sort()
for name in no_heard_and_seen:
    print(name)

주의: 리스트 컴프리헨션에서 readline()을 두 번 호출하면 안 되므로, 먼저 리스트로 받아야 합니다:

# 올바른 방법
no_seen = [readline().rstrip() for _ in range(m)]
no_heard_and_seen = [name for name in no_seen if name in no_heard]

---

시간 및 공간 복잡도

시간 복잡도

• Set 생성: O(N) - 듣도 못한 사람 명단을 Set으로 변환
• 교집합 찾기: O(M) - 보도 못한 사람 명단 순회, 각 in 연산은 O(1)
• 정렬: O(K log K) - K는 교집합의 크기
• 전체: O(N + M + K log K)

공간 복잡도

• Set 저장: O(N) - 듣도 못한 사람 명단
• 결과 리스트: O(K) - 교집합의 크기
• 전체: O(N + K)

---

예제 동작 과정

예제 입력 1: n=3, m=4

입력:

듣도 못한 사람: ["ohhenrie", "charlie", "baesangwook"]
보도 못한 사람: ["obama", "baesangwook", "ohhenrie", "clinton"]

처리 과정:

1. no_heard Set 생성: {"ohhenrie", "charlie", "baesangwook"}
2. 보도 못한 사람 명단 순회:
   • “obama” → Set에 없음 → 무시
   • “baesangwook” → Set에 있음 → 추가
   • “ohhenrie” → Set에 있음 → 추가
   • “clinton” → Set에 없음 → 무시
3. no_heard_and_seen = ["baesangwook", "ohhenrie"]
4. 정렬: ["baesangwook", "ohhenrie"] (이미 사전순)
5. 출력:

   2
   baesangwook
   ohhenrie
   

---

Set의 교집합 연산 활용

Python의 Set은 내장된 교집합 연산을 제공하므로, 더 간단하게 작성할 수 있습니다:

import sys
 
readline = sys.stdin.readline
 
n, m = map(int, readline().rstrip().split())
 
# 듣도 못한 사람 명단
no_heard = {readline().rstrip() for _ in range(n)}
 
# 보도 못한 사람 명단
no_seen = {readline().rstrip() for _ in range(m)}
 
# 교집합 찾기
no_heard_and_seen = sorted(no_heard & no_seen)
 
# 결과 출력
print(len(no_heard_and_seen))
for name in no_heard_and_seen:
    print(name)

장점:

• 코드가 더 간결함
• Set의 내장 연산을 활용

단점:

• 보도 못한 사람 명단도 Set으로 변환해야 하므로 메모리를 더 사용할 수 있음

---

주의사항

1. 입력 최적화

N, M이 최대 500,000이므로 input() 대신 sys.stdin.readline()을 사용해야 합니다.

2. 정렬 순서

문제에서 “사전순으로 출력”하라고 명시되어 있으므로 반드시 정렬해야 합니다.

3. Set 초기화

no_heard = set([])  # 가능
no_heard = set()     # 더 간결

---

관련 알고리즘

• Set을 이용한 교집합 찾기
• Python 입력 최적화
• 확산 추적