백준 1764번 - 듣보잡 [Python]

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

1764번: 듣보잡

안녕하세요, 오늘은 파이썬을 사용하여 백준 1764번 문제인 '듣보잡' 문제를 해결하는 방법에 대해 이야기해보려고 합니다.

 

문제 이해

이 문제는 두 명단에서 중복되는 이름을 찾는 것입니다. 첫 번째 명단에는 듣도 못한 사람들의 이름이 있고, 두 번째 명단에는 보도 못한 사람들의 이름이 있습니다. 우리의 목표는 이 두 명단에서 중복되는 이름을 찾아 출력하는 것입니다.

 

초기 접근

처음에는 아래와 같이 코드를 작성했습니다:

n, m = map(int, input().split())
res = []
for i in range(n):
    a = input()
    res.append(a)

cnt = 0
res2 = []
for i in range(m):
    b = input()

    if b in res:
        cnt += 1
        res2.append(b)

print(cnt)
for i in res2:
    print(i)

이 코드는 두 명단을 각각 리스트로 받아, 두 번째 명단의 각 이름이 첫 번째 명단에 있는지 확인하는 방식으로 작동합니다.

제출을 해보니 시간 초과 에러가 났습니다.

이 방식은 리스트의 크기가 클 경우 매우 비효율적입니다. 리스트에서 특정 요소를 찾는데 필요한 시간 복잡도는 최악의 경우 O(n)이기 때문입니다.

 

최적화

이 문제를 해결하는 더 효율적인 방법은 첫 번째 명단을 set 자료형으로 변환하는 것입니다. Python의 set 자료형은 내부적으로 hash table을 사용하여 요소를 저장하기 때문에, 특정 요소가 set에 포함되어 있는지 확인하는 데에 걸리는 시간 복잡도는 O(1)입니다. 이를 통해 시간 초과를 피할 수 있습니다.

따라서 최적화된 코드는 아래와 같습니다:

n, m = map(int, input().split())
list_n = [input() for _ in range(n)]
list_m = [input() for _ in range(m)]

def solution(n, m, list_n, list_m):
    set_res = set(list_n)
    cnt = 0
    res2 = []
    for b in list_m:
        if b in set_res:
            cnt += 1
            res2.append(b)
    return cnt, sorted(res2)

cnt, res2 = solution(n, m,list_n,list_m)

print(cnt)
for i in res2:
    print(i)

마치며

이렇게 하면, 입력의 크기가 클 경우에도 효율적으로 문제를 해결할 수 있습니다. 이 문제를 통해 Python의 set 자료형의 중요성과 효율적인 데이터 구조 선택의 중요성을 다시 한번 확인하게 되었습니다.

다음에 또 다른 흥미로운 문제를 함께 해결해 보도록 하겠습니다. 감사합니다!