Chapter 7-3 떡볶이 떡 만들기

< 이 글은 책 '이것이 취업을 위한 코딩 테스트다' 에서 발췌한 내용을 인용했습니다. >

 

떡볶이 떡 만들기

 

<무지성 코드>

n, m = map(int, input().split())
array = list(map(int, input().split()))
start = 0
end = max(array)
result = 0

while(start <= end):
    total = 0
    mid = (start + end) // 2

    for i in array:
        if i > mid: total += (i-mid)

    if total < m:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

<답안 예시>

n, m = list(map(int, input().split()))
array = list(map(int, input().split()))

start = 0
end = max(array)

result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for i in array:
        if i > mid: 
            total += i-mid
            
    if total < m:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

 

거의 유사하다. 하나하나 탐색이 필요한 경우(+ 데이터가 정렬된 상태)에서는 이진 탐색을 사용하는게 효율적이라는 것을 알았다.