import sys
input=sys.stdin.readline
N,K=map(int,input().split())
L=[]
for i in range(N):
L.append(int(input()))
L.sort()
start=L[0]
end=L[-1]+K
while start<=end:
count=K
mid=(start+end)//2
for i in range(len(L)):
if L[i]<mid:
count-=mid-L[i]
elif L[i]>=mid:
break
if count>=0:
start=mid+1
else:
end=mid-1
print(end)📌 최대 팀 목표레벨을 어떻게 구할 것인가?
문제에서 핵심적으로 물어보는 내용은 최대 팀 목표 레벨을 구하는 것이다.
하지만 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K의 범위는 (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 이다.
시간복잡도 O(n^2)과 같은 풀이로 시도하면 시간 초과가 발생할수 있기 때문에 이분탐색으로 문제를 풀었다.
그렇다면 다음과 같은 의문이 생긴다.
❓ 이분탐색을 어떻게 탐색할 것인가?
이분탐색을 하기 위해서 일단 리스트 L을 정렬한다. 참고로 다른사람의 풀이를 보면 정렬하지않고 풀수있는 방법이 존재한다.
start와 end값을 잡고 mid값을 잡는다.
내 코드에서의 mid값은 mid 값보다 작은 리스트의 값에서 K를 더한 값이 0보다 크는가?
그렇다면 mid값을 증가시키고 그렇지않으면 감소시킨다.
문제의 예제 입력을 보았을때
K=10 , L=[10,15,20] 이 주어진다. 만약 mid값이 17이라고 해보자.
17보다 작은 리스트의 값은 10 , 15이고 총합은 25이다. 그리고 K값까지 더하면 35이다.
이때 2를 나누면 17.5가 나오고 int형으로 17이라는 값이 나온다.
리스트의 sum을 구한후 길이만큼 나누면 오류가 발생한다.
왜냐하면 20과같이 K값을 전혀 나눠줄 필요없는 원소가 존재하기 때문에 꼭 mid값보다 작은 원소에게 K값을 나눠줘야지 최대값이 나오기 때문이다.
따라서 반복문으로 0번째인덱스부터 len(L)까지 탐색을 한 후 각 리스트값이 mid값보다 작은지 확인한 후
count에다가 mid-L[i]를 빼준다.
✅ 코드에서 중요한 부분
- start=L[0] ; end=L[-1]+K 로 잡아준다.
- count 초기값또한 K로 잡아준다.
- 최대 레벨을 출력해야하므로 end를 출력한다.
