[TAVE/이코테] ch07 이진 탐색 | 실전 문제

참고자료: 이것이 코딩테스트다

실전 - 부품 찾기

store_component_count = int(input())
store_component = list(map(int, input().split()))
customer_component_count = int(input())
customer_component = list(map(int, input().split()))

#정렬
store_component.sort()
customer_component.sort()

def binary_search(start, end, goal):
    mid = end // 2
    if goal == store_component[start]:
        return start
    elif goal == store_component[mid]:
        return mid
    elif goal > store_component[end] or goal < store_component[start]:
        return TypeError

    if goal < store_component[mid]:
        end = mid - 1
        binary_search(start, end, goal)
    elif goal > store_component[mid]:
        start = mid + 1
        binary_search(start, end, goal)


start = 0
for component in customer_component:
    store_index = binary_search(start, len(store_component) - 1, component)

    #손님이 찾는 부품이 없으면 None 반환하는 상황을 고려해 if문 작성
    if store_index is not None:
        #시작점을 반환받은 start로 지정한다. 
        #customer_component도 정렬되어 있기 때문에 이미 찾은 이전 원소(customer_component)보다 작은 store_component를 탐색할 필요가 없다.
        start = store_index
        print('yes', end=' ')
    else: 
        print('no', end=' ')

• 먼저 동빈이네 매장 부품 리스트인 store_component리스트와 손님이 찾는 부품 리스트인 customer_component를 정렬했다. 
• 이진 탐색을 진행할 binary_search 함수를 만들었다.
• for문으로 customer_component를 돌리면서 손님이 찾고 싶은 부품을 하나씩 binary_search함수에 넣어 탐색했다. 이 때 시작점을 함수의 return값으로 계속 갱신했다.

🐰customer_component 리스트도 정렬을 해놨기 때문에 남은 원소들은 무조건 이전에 탐색한 원소보다 큰 수이다. 때문에 binary_search 함수에 넣을 때 반환받은 시작점 인덱스 이전의 원소는 볼 필요가 없기 때문에 계속해서 갱신했다.

실전 - 떡볶이 떡 만들기

rice_cake_count, customer_request_count = map(int, input().split())
rice_cake_list = list(map(int, input().split()))

longest = max(rice_cake_list)
for length in range(longest - 1, 0, -1):
    cut_rice_cake = 0
    for rice_cake in rice_cake_list:
        if rice_cake > length:
            cut_rice_cake += rice_cake - length
    if cut_rice_cake >= customer_request_count:
        print(length)
        break

👉🏻이진법을 도대체 어디에 사용해야하는지 감이 안 와서 내 식대로 풀어버렸다..ㅎ..

• 절단기로 자를 높이는 가장 긴 떡을 기준으로 1씩 줄여간다.
• 떡이 절단기에 설정된 높이보다 크면 잘린 떡의 길이를 cut_rice_cake에 더해준다.
• cut_rice_cake이 손님이 요청한 길이보다 크거나 같으면 출력한다.

📚책 풀이

👉🏻해당 문제는 파라메트릭 서치 유형의 문제이다. 파라메트릭 서치란 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.

👉🏻절단기의 높이 범위가 10억이라는 큰 수까지라는 것을 보면 바로 이진탐색을 떠올려야 한다.

👉🏻위와 같은 방식으로 시작점은 0, 끝점은 가장 긴 떡의 길이로 설정한다. 그리고 중간부터 자른다고 가정해 잘린 떡의 길이를 판별한다.

rice_cake_count, customer_request_count = map(int, input().split())
rice_cake_list = list(map(int, input().split()))

start = 0
end = max(rice_cake_list)

result = 0
while(start <= end):
    mid = (start + end) // 2
    cutting = 0
    for rice_cake in rice_cake_list:
        if rice_cake > mid:
            cutting += (rice_cake - mid)
    if cutting < customer_request_count:
        end = (mid - 1)
    elif cutting > customer_request_count:
        result = mid #최대한 덜 잘랐을 때가 정답이므로, 여기서 result에 기록한다.
        start = (mid + 1)

print(result)

🐰푸는 방식을 엿보고 코드를 짜보았는데 result에 값을 따로 적는 부분을 놓쳤다. 잘린 떡들이 손님이 요청한 길이와 딱 맞아떨어지지 않을 경우를 대비해 잘린 떡이 손님이 요청한 길이보다 클 때마다 result에 기록해둔다.