💡문제접근
- 이 문제의 알고리즘이 어떻게 이분 탐색이 나왔는지 잘 몰라서 처음에는 좀 당황스러웠다.
- 이분 탐색 알고리즘을 구현한 함수와
bisect방식에 의한 이분 탐색 두 가지 방법을 이용해서 해결해보려고 노력했고 두 방법에 대해서 확실히 알 수 있었던 좋은 문제였다.
💡코드1(메모리 : 44104KB, 시간 : 280ms)
- 아래의 코드는
bisect방식을 활용한 방법이다.
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
N, M = map(int, input().strip().split())
title = []
damage = []
for i in range(N):
status, val = map(str, input().strip().split())
val = int(val)
title.append(status)
damage.append(val)
for i in range(M):
print(title[bisect_left(damage, int(input()))])💡코드2(메모리 : 42036KB, 시간 : 404ms)
- 아래의 코드는 이분 탐색 알고리즘을 구현한 코드이다.
import sys
input = sys.stdin.readline
N, M = map(int, input().strip().split())
title = []
damage = []
for i in range(N):
status, val = map(str, input().strip().split())
val = int(val)
title.append(status)
damage.append(val)
def binary_search(target):
start = 0
end = len(damage)-1
while start <= end:
mid = (start + end) // 2
if target > damage[mid]:
start = mid + 1
else:
end = mid - 1
return title[end+1]
for _ in range(M):
tmp = int(input())
print(binary_search(tmp))📌 bisect 배열 이진 분할 알고리즘
- 파이썬 이진 탐색 라이브러리로
bisect_left와bisect_right가 있다.- 이
bisect라이브러리는 이미 정렬된 상태여야 적용이 가능하다.
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x)) # 2
print(bisect_right(a, x)) # 4
bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽의 위치를 반환함bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽의 위치를 반환함
💡소요시간 : 27m
🐢