[백준] 시간초과

2805 나무자르기 / Python

N이 백만이기 때문에 N크기의 리스트를 끝에서부터 돌면서 확인하는 것은 시간복잡도가 n^2

-> 이분 탐색으로 mid값을 잡으면서 계산

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

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

cut = max(tree) - (M//len(tree)+1)

get = 0

while get < M:

    get = sum([x-cut for x in tree if x-cut > 0])

    cut -= 1

print(cut+1)

 

이전 코드: 나무 최대 길이부터 M값이 될때까지 1씩 빼면서 나무 모음

 

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

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

start = 0

end = max(tree)

while start <= end:

    mid = (start + end) // 2

    get = sum(i - mid if i - mid > 0 else 0 for i in tree)

    if get < M:

        end = mid - 1

    else:

        start = mid + 1

print(end)

 

이분 탐색(Binary Search)는 정렬된 수열에서 검색하는 알고리즘

시간복잡도는 탐색할 범위를 절반으로 줄여서 탐색하므로 O(logn)

 

11723 집합 / Python

type-casting 하는데도 시간이 걸리나봐

all에서 i를 문자열로 타입캐스팅 했을 때 시간초과 나서 int 그대로 사용했더니 성공

set([str(x) for x in range(1,21)])

-> set([x for x in range(1,21)])