[이분탐색] 백준 2805. 나무자르기

문제

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

이분탐색인 걸 알아보고, 풀어야지만 맞을 수 있는 문제였다.
내 코드는 아무리 개선을 해도, pypy에서만 시간초과가 안 났고, 다른 분 코드를 보니 collections 모듈의 Counter 클래스를 임포트했더라.

counter 임포트 보다 나무 자른 길이의 합을 한줄 sum으로 표현한 게 결정적이었다.

Counter

collections 모듈의 Counter 클래스
https://www.daleseo.com/python-collections-counter/
https://docs.python.org/3/library/collections.html#collections.Counter
Counter 클래스는 배열의 값들을 dictionary의 원리를 이용해, 더 빨리 정렬하거나 계산해준다. (빈도에 따른 most를 찾거나, 큰 값 찾을 때 빠르다. ex. most_common이라는 메서드)
dictionary는 일반 배열에 비해 자료 찾을 때 더 효율적인 자료구조이기 때문이다..(향후 상세 포스팅)

틀린 코드 - 시간초과 (이분탐색 안함)

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
# n 나무수, m 가져갈 길이

tree = list(map(int, input().split()))
cut = max(tree)

while True :
    tot = 0
    # print(cut, end=' ')
    for t in tree:
        res = (t-cut if t>=cut else 0)
        tot += res

    if tot >= m:
        print(cut)
        break
    cut -= 1

맞은 코드 - but, pypy에서만 시간초과가 안남

import sys
input = sys.stdin.readline

# n 나무수, m 가져갈 길이
n,m = map(int, input().split())
tree = list(map(int, input().split()))

# cut의 범위는 max tree ~ 1
small = 1
big = max(tree)
ans = 0
while small <= big:
    tot = 0
    mid = (big+small)//2
    for t in tree:
        tot += (t-mid if t>=mid else 0)

    if tot >= m:
        small = mid+1
        ans = mid

    else:
        big = mid-1
print(ans)

참고 코드 ( Counter 사용 )

import sys
from collections import Counter

N, M = map(int, sys.stdin.readline().split())
trees = Counter(map(int, sys.stdin.readline().split()))
s = 1
e = max(trees)

while s <= e:
    m = (s + e) // 2
    total = sum((h - m) * i for h, i in trees.items() if h > m)
    if total >= M:
        s = m + 1
    elif total < M:
        e = m - 1

print(e)

 

+ 한 줄짜리 sum 변수 만들기

# if조건이 맨 뒤, .items()로 꺼내서 sum으로 씌워줌
	tot = sum((h-mid)*i for h,i in t.items() if h>mid)

# 조건에 맞는 리스트 만들어서, sum해줌
    tot = sum([tt-mid if tt>=mid else 0 for tt in t])