이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
이미 정렬이 되어있어야 사용이 가능함
떡볶이 떡 만들기
출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬
문제 설명
오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 총 길이가 M일 때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하세요.
입력 조건
- 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 <= N <= 1,000,000, 1 <= M <= 2,000,000,000)
- 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다.
- 높이는 10억보다 작거나 같은 양의 정수 또는 0 이다.
출력 조건
- 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
예시
입력
4 6
19 15 10 17출력
15우선 순차 탐색으로 풀어보자.
순차 탐색 풀이
# 떡볶이 떡 만들기
# 순차 탐색
n, m = map(int, input().split())
h_list = list(map(int, input().split()))
h = max(h_list)
total = 0
while True:
for val in h_list:
total += max(val - h, 0)
if total >= m:
print(h)
break
else:
total = 0
h -= 1이렇게 해도 예시 케이스 정도는 답이 나오지만 문제의 입력 조건을 보자.
탐색 범위는 0부터 변수 h가 되는데, 최악의 경우 범위가 10억이 된다.
(10억으로 시작해서 1씩 낮아지면서 탐색함)
이정도 범위면 무조건 시간초과가 나오므로 이진 탐색을 반드시 고려해야 한다.
이진 탐색 풀이
# 떡볶이 떡 만들기
# 이진 탐색
n, m = map(int, input().split())
h_list = list(map(int, input().split()))
start = 0
end = max(h_list)
while start <= end:
total = 0
mid = (start + end) // 2
for val in h_list:
total += max(val - mid, 0)
# 자르고 나온 떡 길이의 합이 손님이 요청한 양에 못 미침
# 무조건 더 늘려야 함
if total < m:
end = mid - 1
# 자르고 나온 떡 길이의 합이 손님이 요청한 양과 같거나 더 많음
# 높이의 최댓값이 될 가능성이 있으니까 result에 담고,
# 자르고 나온 떡의 길이를 줄여보기 (높이의 최댓값 구하기)
else:
result = mid
start = mid + 1
print(result)처음 탐색 범위는 0부터 end의 초기값이 되는데, 최악의 경우로 범위가 10억이라도, 범위를 절반씩 줄여서 훨씬 빨리 탐색한다.
(10억 -> 5억 -> 2억 5천만 -> ...)
주석에 나와있는 것처럼 mid 값을 활용해서 result값으로 계속 변동시켜 조건에 만족하는 최댓값을 찾는다.
bisect 함수 알아가기
파이썬에서 이진 탐색을 수행할 때 쓰기 좋은 bisect 함수를 알아보자.
bisect 함수
bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환
이 함수를 이용해서 정렬된 배열에서 특정 수의 개수를 구해보자.
해당 수가 배열에 존재하지 않을 경우 -1을 반환하기
예시
입력
2
1 1 2 2 2 2 3출력
4from bisect import bisect_left, bisect_right
x = int(input())
array = list(map(int, input().split()))
result = bisect_right(array, x) - bisect_left(array, x)
if result == 0:
print(-1)
else:
print(result)예시 케이스로 보면 반환 값이 다음과 같다.
bisect_right(array, x) : 6
bisect_left(array, x) : 2
