[백준] 이분탐색, 16564 히오스 프로게이머(파이썬)

카테고리를 제공하는 백준 문제를 접하게 되는 경우, '이분탐색으로 풀어야지!' 라고 생각하기 쉽다. 그러나 카테고리가 주어지지 않는 문제이거나, 현업에서 이슈가 발생하는 경우 이분탐색에 대한 개념이 잡혀있지 않다면 어려움을 겪을 수 있을 거 같다.

그렇다면, 이분탐색은 언제 사용하면 좋을까?

이분탐색(binary search)이란?
데이터가 정렬되어 있는 배열에서 원하는 값을 탐색할 때 쓰면 좋은 알고리즘

이분탐색을 사용하는 이유는, 처음부터 끝까지 탐색을 진행하는 '선형탐색'과 달리, 최소값(pl), 중간값(pc), 최대값(pr)을 선언한 이후 값의 범위를 통해 pl, pr 값을 옮겨가며 탐색하기 때문에 복잡도를 낮추기에 유리하다.

복잡도(complexity)란?
복잡도는 시간복잡도(실행시간), 공간복잡도(필요한 메모리와 파일 공간)로 구성되는데 알고리즘의 성능을 객관적으로 평가하는 기준이다.

백준 16564 히오스 프로게이머 문제를 만났을 때, 코드 설계를 다음과 같이 예상하였다.

1. 이진탐색을 위해 sort()를 통한 오름차순 정렬
2. '레벨' 개념의 start(pl), end(pr), mid(pc) 값 선언
3. 함수 선언을 통한 복잡도 낮추기
4. 목표하는 최소 레벨(mid)이 T에 가까워질 때까지 while문 작성
5. 결과값 출력

import sys

n, k = map(int, input().split())

insert_list = list(int(sys.stdin.readline()) for _ in range(n))
insert_list.sort() # 정렬


start = min(insert_list)
end = start + k # 최소 레벨에 경험치 다 넣고도 최소값일수도 있기 때문


def HOS(alist, start, end) :
    res = 0
    while start <= end :
        mid = (start + end) // 2    # 목표하는 레벨

        sum = 0 # 내가 쓸 경험치
        for level in insert_list: # 리스트 돌려서 목표레벨(mid)까지 올려보자
            if mid > level : # 목표레벨보다 리스트에있는 레벨이 낮으면
                sum += (mid - level) # sum 만큼 경험치를 써라
        
        # for문이 다 돌고 나오면 목표레벨까지 쓴 경험치(sum)이 나올 거고 
        
        # 경험치(sum)를 다 쓰거나 덜 쓰면
        if sum <= k :
            start = mid + 1
            res = max(mid, res) # 목표레벨 mid를 결과값 res로 출력

        # 경험치(sum)를 다 써버림. 즉 목표레벨이 너무 높았다는 것. end를 (목표레벨 - 1)로 설정하고 다시 위로
        else : 
            end = mid - 1

    print(res)

HOS(insert_list, start, end)