[백준] 1764번: 듣보잡 (🥈실버 4) (Python)

문제 바로 가기

1764번: 듣보잡

 

---

풀이

• 사용 언어 : Python
• 풀이한 날짜 : 2024-01-11

 

n, m = tuple(map(int, input().split()))

not_heard = [
    input()
    for _ in range(n)
]

not_seen = [
    input()
    for _ in range(m)
]

not_heard = set(not_heard)
not_seen = set(not_seen)

answer = not_heard.intersection(not_seen)

# for elem in not_seen:
#     if elem in not_heard:
#         answer.append(elem)

answer = list(answer)
answer.sort()

print(len(answer))
for elem in answer:
    print(elem)

 

풀이 로직

• '듣도 못한 사람'과 '보도 못한 사람'의 교집합에 해당하는 사람들을 완전 탐색을 통해 구한다.
• 다만, 리스트(배열) 자료구조를 활용하면 시간 초과가 발생하기 때문에 해시 테이블(파이썬에선 set이나 딕셔너리)을 사용하여 문제를 해결해주어야 한다.
• 파이썬의 set를 활용, 내부 함수인 intersection을 통해 두 집합의 교집합을 구한 후, sort()를 통해 사전 순으로 정렬하여 문제를 해결하였다. 

 

문제 접근 과정 및 느낀점

해시 함수의 특징은 이해하고 있었으나, 이를 알고리즘 문제 해결에 활용해본 적이 없어 난항을 조금 겪었던 문제였다.

이번 기회가 좋은 경험이 되었다고 생각한다.