[백준] 1764번 듣보잡, 시간초과

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

1764번: 듣보잡

 

set 사용해서 제대로 푼 것 같은데 자꾸 시간초과가 나온다.

# BOJ_1764
import sys

# 입력
n, m = map(int, sys.stdin.readline().split())
names = []
for _ in range(n + m):
    name = sys.stdin.readline()
    names.append(name)

# 중복된 원소 찾기
names.sort()
overlap = []
for i in range(len(names)):
    if names.count(names[i]) > 1:
        overlap.append(names[i])

# 듣보잡 수와 명단 출력하기
overlap = set(overlap)
print(len(overlap))
for name in overlap:
    print(name)

 

 

찾아보니 이분탐색으로 (logn) 정도 시간복잡도를 낮춰야 통과가 된다고 한다.

 

 

이분탐색으로 바꾸고

입력할 때 strip()을 추가해주었다.

# BOJ_1764
import sys

# 입력
n, m = map(int, sys.stdin.readline().split())
hear_names = []
see_names = []
for _ in range(n):
    name = sys.stdin.readline().strip()
    hear_names.append(name)


for _ in range(m):
    name = sys.stdin.readline().strip()
    see_names.append(name)

hear_names.sort()
overlap = []
for name in see_names:
    left = 0
    right = len(hear_names) - 1
    while left <= right:
        mid = (left + right) // 2
        if hear_names[mid] < name:
            left = mid + 1
        elif hear_names[mid] > name:
            right = mid - 1
        else: # names[mid] == name
            overlap.append(name)
            break

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

 

이분 탐색할 때 이부분 주의

for name in see_names:
    left = 0
    right = len(hear_names) - 1

hear_names라는 듣지 못한 사람 리스트에서 보지 못한 한 사람 이름을 찾는 거이므로

right는 hear_names의 마지막 인덱스까지 잡아주면 된다.

 

 

이분 탐색 구현은 이 블로그 참고했다.

https://velog.io/@madfinger/Binary-Search%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8C%8C%EC%9D%B4%EC%8D%AC

 

숨겨진 디테일이 많았던 문제..