boj 2805

문제

https://www.acmicpc.net/problem/2805

풀이

import sys
input = sys.stdin.readline
from collections import Counter

n,m = map(int,input().split())
arr = Counter(map(int,input().split()))

k = max(arr)

def check(x):
  length = 0
  for i, val in arr.items():
    if i > x:
      length += (i - x) * val

  return length

minn = 0
maxx = k
answer = 0

while(minn <= maxx):

  x  = (minn + maxx) //2
  result = check(x)

  if result < m:
    maxx = x-1

  else :
    answer = x
    minn = x+1

print(answer)

공부한것

이분탐색 할때 범위 이동

min, max를 x+1, x-1 이 아니라 x로 옮기면 틀린다
다음 범위로 해줘야 정상적으로 탐색되나보다

Counter

python 라이브러리중에 Counter를 정말 오랜만에 써봤다.
거의 안쓰는애라 써봤는지 조차 가물가물한데
가끔 필요할때 쓰면 좋을것같다

물론 dict로 그냥 counter를 구현해도 상관없다.

Counter('hello world') 

# Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

요런식으로 문자열이나 배열같은걸 넣으면 구성 원소들의 개수를 dict로 다 뽑아준다.

이 문제도 모든 배열원소를 직접 비교하면서 길이를 구해도 되지만, 개수가 커지다 보면 겹치는 중복값이 많기에 counter를 하나 계산해서 만들고, 중복값은 * 연산으로 처리하는게 더 빠른것같다.

끝!