[백준] 1764번 파이썬 (듣보잡)

1. 문제와 예제

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

1764번: 듣보잡

 

문제

예제

---

2. 전체 코드

1) set 사용

import sys
input = sys.stdin.readline

# 입력 받기
N, M = map(int, input().split()) # 듣도 못한 사람 수, 보도 못한 사람 수

# 듣도 못한 사람 집합 생성
a = set()
for _ in range(N):
    a.add(input().rstrip())

# 보도 못한 사람 집합 생성
b = set()
for _ in range(M):
    b.add(input().rstrip())

res = sorted(list(a & b)) # 듣보잡 리스트 생성, 정렬

# 결과 출력하기
print(len(res)) # 듣보잡 수

for i in res:
    print(i) # 듣보잡 명단 출력

 

2) dict, list 섞어 사용

import sys
input = sys.stdin.readline

# 입력 받기
N, M = map(int, input().split()) # 듣도 못한 사람 수, 보도 못한 사람 수
dct = {} # 듣도 못한 사람 dict
lst = [] # 듣도 보도 못한 사람 리스트
cnt = 0 # 듣도 보도 못한 사람 수

# 듣도 못한 사람 dict 생성
for i in range(N):
    dct[input().rstrip()] = True

# 듣도 보도 못한 사람 리스트 생성
for i in range(M):
    name = input().rstrip() # 이름
    if name in dct:
        lst.append(name)
        cnt += 1

lst.sort() # 사전순으로 출력 위해 정렬

# 결과 출력하기
print(cnt) # 듣보잡 수

for i in lst:
    print(i) # 듣보잡 명단 출력

---

3. 코드 해설

집합을 사용하는 게 효율적일 때가 자주 있는 것 같다. 중복을 없애주는 기능뿐만 아니라 집합 연산(이 문제에서는 '&')도 사용할 수 있고 1920번(수 찾기) 문제에서 봤을 때도 set의 in 연산을 통한 포함 여부 확인의 시간 복잡도가 O(1)으로 시간적으로 빨랐다.