[백준] 19637번 IF문 좀 대신 써줘 ★

💡문제접근

• 이 문제의 알고리즘이 어떻게 이분 탐색이 나왔는지 잘 몰라서 처음에는 좀 당황스러웠다.
• 이분 탐색 알고리즘을 구현한 함수와 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