BOJ 1764. 듣보잡 (Python)

BOJ 1764. 듣보잡

1764번: 듣보잡 (acmicpc.net)

1764번: 듣보잡

풀이

파이썬의 x in y를 이용해서 풀었더니 시간 초과가 났다.

 

N과 M이 500,000 이하의 큰 수라 연산하는 것이 오래걸리나 싶어서 탐색을 이진탐색 으로 바꾸어 풀었다.

 

이진탐색(binary seart)는 O(NlogN)
파이썬 내장함수 sort()는 O(logN)이므로 이진탐색이 더 좋다.

def binary_search(start, end, list, target, result):
    if start > end:
        return

    mid = ( start + end ) // 2

    if list[mid] == target:
        heapq.heappush(result, target)
    if list[mid] > target:
        end = mid - 1
        binary_search(start, end, list, target, result)
    if list[mid] < target:
        start = mid + 1
        binary_search(start, end, list, target, result)

1. 탐색하고자 하는 리스트를 오름차순으로 정리한다.
2. target < 중앙값 이면 target은 중앙값의 왼쪽에 있으므로 end(index)를 중앙값index - 1 로 설정하고 중앙값의 오른쪽은 버린다.
3. 중앙값 < target 이면 target은 중앙값의 오른쪽에 있으므로 start(index)를 중앙값index + 1 로 설정하고 중앙값의 왼쪽은 4. 이를 반복한다.
4. 중앙값이 target과 일치한다면 found. 종료
5. 종료되지 못하고 end < start가 되면 탐색 실패. not found

의 절차를 따른다.

여기서 가장 중요한 점은 탐색하고자 하는 리스트가 반드시 정렬되어 있어야 한다는 것이다. 잊지말자!

 

 

또한 sort()를 사용하지 않고 오름차순으로 정렬한 값을 출력하기 위해서 heapq를 사용했다.

 

• heapq 모듈 (최소, 최대 힙)

소스코드

import sys
import heapq

def binary_search(start, end, list, target, result):
    if start > end:
        return

    mid = ( start + end ) // 2

    if list[mid] == target:
        heapq.heappush(result, target)
    if list[mid] > target:
        end = mid - 1
        binary_search(start, end, list, target, result)
    if list[mid] < target:
        start = mid + 1
        binary_search(start, end, list, target, result)

result = []
hear = []

N, M = map(int, input().split())

for _ in range(N):
    hear.append(sys.stdin.readline().rstrip())

l = len(hear)
hear.sort()

for _ in range(M):
    see = sys.stdin.readline().rstrip()
    binary_search(0, l-1, hear, see, result)

print(len(result))
while result:
    print(heapq.heappop(result))