글 읽기 - 파이썬 시간초과 질문입니다ㅠㅠ

qute726 3년 전 0

이분 탐색의 방법으로 풀었고, pypy3으로 제출했을 땐 통과지만, python3 로 넣으면 시간초과가 뜹니다.ㅠㅠ

혹시 python 으로 넣었을 때 시간초과 안뜨는 방법이 있을까요??

어느 부분에서 코드를 수정해야할지 감이 안옵니다..ㅠㅠㅠㅠ 도와주시면 감사하겠습니다

import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
List=list(map(int,sys.stdin.readline().rstrip().split()))

start=0
end=max(List)
result=0

while start<=end:
    mid=(start+end)//2
    total=0

    for i in List:
        if i>=mid:
            total+=i-mid

    if total >= m:
        start=mid+1
        result=mid
    else:
        end=mid-1

print(result)

wider93 3년 전 1

14~16번 줄을 더 빠르게 해야 합니다. 모든 나무에 대해 mid보다 큰지 물어보지 않을 수 있는 방법을 찾아보시면 됩니다.

qute726 3년 전 0

답변 달아주신 것 보고, 14-16번 줄을 변경해야겠다 싶어.. 말씀하신 방법은 아닌 것 같지만

14-16번 줄을 total=sum([i-mid if mid < i else 0 for i in List]) 로 바꾸어 해결했습니다 !!

모든 나무에 대해 mid 보다 큰지 물어보지 않을 수 있는 방법에대해선 조금 더 생각해보려고합니다

감사합니다 !!!

quf9484 3년 전 1

5번째 줄 코드가 더 빠른 이유가 궁금합닌다.

List Comprehension이 빠른 것은 이해했지만, sum함수를 쓰기 위해서 n만큼 시간 복잡도가 추가 되는데 오히려 늦어지는 거 아닌가요?

for i in List:
    if i>=mid:
        total+=i-mid
        
total=sum([i-mid if mid < i else 0 for i in List])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 시간초과 질문입니다ㅠㅠ

qute726 3년 전 0

wider93 3년 전 1

qute726 3년 전 0

quf9484 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말