(Python) 이진 탐색 실전 문제2

본 글은 “이것이 취업을 위한 코딩 테스트다 with 파이썬” 교재를 참고한 것임

문제

문제풀이

전형적인 이진 탐색 문제이자 파라메트릭 서치(parametric search) 유형의 문제이다. 파라메트릭 서치는 최적화 문제를 결정 문제(’예’, ‘아니오’로 답하는 문제)로 바꾸어 해결하는 기법이다.

범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다. 코딩 테스트나 프로그래밍 대회에서는 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다.

이 문제의 풀이 아이디어는 적절한 높이를 찾을 때까지 절단기의 높이 h를 반복해서 조정하는 것이다. ‘현재 이 높이로 자르면 조건을 만족할 수 있는가?’를 확인한 뒤에 조건의 만족 여부(’예’, ‘아니오’)에 따라서 탐색 범위를 좁혀 나간다.

절단기의 높이(탐색 범위)는 1부터 10억까지의 정수 중 하나인데, 탐색 범위가 매우 크기 때문에 이진 탐색을 떠올렸다. 높이 범위가 한정적이었다면 순차 탐색으로도 해결할 수 있지만, 이 문제에서 높이는 최대 10억까지의 정수이므로 순차 탐색은 시간 초과를 받을 것이다.

반면 높이를 이진 탐색으로 찾는다면 대략 31번 만에 모든 경우의 수를 고려할 수 있다. 떡의 개수가 최대 100만 개이므로 절단기 높이를 바꿀 때마다 모든 떡을 체크하는 경우 대략 최대 3,000만 번 정도의 연산으로 문제를 풀 수 있다.

소스코드

내풀이

# 문제 범위가 너무 크다(10억) -> 이진 탐색?

# 잘랐을 때의 떡의 양 계산하는 함수
def cutting(arr, h, n):
    total = 0
    for i in range(n):
        if arr[i] > h:
            total += arr[i] - h
    return total

# def cutting(arr, h):
#     for i in range(len(arr)):
#         temp = arr[i]- h
#         if temp < 0:
#             arr[i] = 0
#         else:
#             arr[i] = temp
#     return sum(arr)

# 떡의 개수 N, 요청한 떡의 길이 M 입력받기
n, m = map(int, input().split(' '))
# 개별 떡의 높이
arr = list(map(int, input().split(' ')))

start = 0
end = max(arr)
h_list = []
while start <= end :
    h = ( start + end ) // 2

    # 요청한 떡의 길이보다 작은 경우 왼쪽 확인
    if cutting(arr, h) < m :
        end = h - 1

    # 요청한 떡의 길이보다 충분한 경우 오른쪽 확인
    else : # cutting(arr, h) >= m
        h_list.append(h) # 최소한 m이 나오면 되고 최대의 h를 구해야 하므로
        start = h + 1

print(h_list)
print(max(h_list))

교재풀이도 내풀이와 비슷했으므로 따로 첨부를 하지 않는다.

잘랐을 때의 떡의 양 계산하는 cutting() 함수를 구현하여 찾고자 하는 절단기의 높이 h를 이진 탐색으로 찾는다.

절단기의 높이 h는 0부터 가장 긴 떡의 길이 안에 있어야 한다. 따라서 end는 입력받은 떡 길이 중 제일 긴 떡의 길이로 한다.

현재 절단기 높이에서 만들어지는 떡의 양이 요청한 떡의 양보다 적은 경우 절단기 높이를 작게 해야 하므로 왼쪽을 탐색한다.

현재 절단기 높이에서 만들어지는 떡의 양이 요청한 떡의 양보다 충분한 경우, 최소한 m이 나오면 되고 그중 최대의 h를 구하라는 게 문제이므로 h를 절단기 높이의 후보 리스트인 h_list에 추가해준다. 그리고 절단기 높이를 크게 해보기 위해 오른쪽을 탐색한다.

설명을 덧붙이면, if 조건문에서 cutting(arr, h) == m 으로 조건을 안 한 이유는 최소한 m이 나오면 되고 그중 최대의 h를 구하라는 게 문제이기 때문에 cutting(arr, h) >= m 이기만 하면 h_list에 추가한 것이다.

또한 주석 처리된 cutting() 함수는 내가 처음에 작성한 함수인데 저렇게 작성하면 입력받은 원본 arr 함수까지 수정되기 때문에 함수 안에서 따로 리스트를 선언해주거나 원본 값을 변경시키지 않도록 주의해야 할 것 같다.