[백준 문제풀이] 1764 듣보잡 - 파이썬

백준 1764번 - 듣보잡 문제 풀이 및 최적화

1. 문제 접근 방식

처음에는 문제를 가장 직관적인 방식으로 접근했습니다. 두 개의 리스트를 만들어서 각각의 입력을 받고, 첫 번째 리스트의 각 요소가 두 번째 리스트에 있는지 확인하는 방식으로 구현했습니다.

최초 작성 코드

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

N = []
M = []

for _ in range(n):
    txt = input()
    N.append(txt)

for _ in range(m):
    txt = input()
    M.append(txt)

count = 0
result = []
for i in N :
    if i in M :
        count += 1
        result.append(i)

result.sort()
print(count)
for i in result:
    print(i)

2. 발생한 문제점

이 코드를 제출했을 때 "시간 초과" 오류가 발생했습니다. 코드의 로직 자체는 정확했지만, 실행 시간이 문제의 제한 시간을 초과한 것입니다.

시간 복잡도 분석

문제가 된 부분은 다음 코드 블록입니다:

for i in N :
    if i in M :
        count += 1
        result.append(i)

이 부분의 시간 복잡도를 분석해보면:

1. for i in N은 N의 길이만큼 반복 (O(n))
2. 각 반복마다 if i in M에서 M의 길이만큼 검색 (O(m))
3. 결과적으로 전체 시간 복잡도는 O(n*m)

리스트에서 in 연산자를 사용할 때, 파이썬은 리스트의 처음부터 끝까지 순차적으로 검색을 수행합니다. 이는 리스트의 크기가 커질수록 검색 시간이 선형적으로 증가한다는 것을 의미합니다.

3. 개선된 해결 방안

문제를 해결하기 위해 다음과 같이 코드를 수정했습니다:

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

N = set()  # 리스트 대신 set 사용
M = set()  # 리스트 대신 set 사용

for _ in range(n):
    N.add(input())

for _ in range(m):
    M.add(input())

result = sorted(N & M)  # 교집합 후 정렬

print(len(result))
for name in result:
    print(name)

개선 포인트 설명

1. 자료구조 변경: list 대신 set 사용
   • set은 해시 테이블을 기반으로 구현되어 있어 검색 연산의 시간 복잡도가 O(1)입니다.
   • 중복된 원소를 자동으로 제거해주는 특성도 있습니다.
2. 검색 방식 개선: in 연산자 대신 집합 연산자 사용
   • & 연산자를 사용하여 두 집합의 교집합을 구합니다.
   • 이는 개별 검색보다 훨씬 효율적입니다.
3. 코드 간소화
   • count 변수 대신 len() 함수 사용
   • 중간 과정을 줄이고 직관적인 코드로 변경

시간 복잡도 비교

• 기존 코드: O(n*m)
  • n과 m의 크기가 커질수록 실행 시간이 기하급수적으로 증가
• 개선된 코드: O((n+m)log(k)) (k는 교집합의 크기)
  • 입력 받기: O(n+m)
  • 교집합 연산: O(min(n,m))
  • 정렬: O(klog(k))

4. 결론

이 문제를 통해 알 수 있는 중요한 점들:

1. 적절한 자료구조 선택의 중요성
2. 파이썬의 내장 자료구조와 연산자의 시간 복잡도를 이해하는 것의 중요성
3. 문제 해결 시 시간 복잡도를 고려한 접근의 필요성

이러한 최적화를 통해 시간 초과 없이 문제를 성공적으로 해결할 수 있었습니다.