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

albatore 3년 전 0

input도 sys.stdin.readline으로 대체하면서 입력시간 줄였는데도 시간 초과가 뜹니다. 어떻게 해야 시간초과가 뜨지 않을까요 ㅠ

import sys

N = int(sys.stdin.readline())
Numlist = []
Sum = 0
for i in range(0, N):
    Numlist.append(int(sys.stdin.readline()))

for i in range(0, N):
    Sum += Numlist[i]
print(int(round(Sum / N, 0)))

Numlist.sort()
print(Numlist[int(N/2)])

Setlist = list(set(Numlist))
Setlist.sort()
repeat = 1
overlap = []   
for i in Setlist:
    Temp = Numlist.count(i)
    if Temp == repeat:
        overlap.append(i)
    elif Temp > repeat:
        repeat = Temp
        overlap = []
        overlap.append(i)
if len(overlap) == 1:
    print(overlap[0])
else:
    print(overlap[1])
    
if N == 1:
    print(0)
else:
    print(max(Numlist) - min(Numlist))

happiness96 3년 전 3

시간을 많이 잡아먹는 부분이 Numlist, Setlist를 sort하는 부분, Numlist.count 부분으로 예상되는데

정렬하는 부분보다는 반복문을 돌면서 count하는 부분에서 훨씬 더 많은 시간이 소요될겁니다.

최악의 경우 Numlist에는 50만개의 숫자, Setlist에는 8000개, 정확히는 7999개의 숫자가 들어있는데

50만개의 숫자 중 한 숫자의 개수를 찾기 위해 O(N)의 시간의 소요됩니다. 즉 50만개를 다 돌면서 카운팅을 한다는 말이에요.

반복문을 돌면서 8000개의 숫자를 counting 해야하니 20억개의 값들을 탐색해야하는 꼴이 돼버려요.

문제에서 출력을 요구하는 네가지 값들을 하나하나 구하는 것 보다 여러개를 한번에 찾을 수 있는 방법이 없을지 한번 고민해보시면 좋을 것 같아요.

albatore 3년 전 0

감사합니다

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

문제

문제

출처

ICPC

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

albatore 3년 전 0

happiness96 3년 전 3

albatore 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말