글 읽기 - 파이썬 시간초과 에러

mechauk 1년 전 0

정답 자체는 나오는거같은데 시간초과가 뜨네요.

어디 부분을 개선해야 시간을 줄일수있을까요?

import sys
N=int(sys.stdin.readline())
N_list=[]
for i in range(N):
    a=int(sys.stdin.readline())
    N_list.append(a)


avg1= sum(N_list)/len(N_list) ### 산술평균 계산
avg1=round(avg1) ### 반올림

N_list.sort() ### 정수 정렬
avg2=N_list[int((N-1)/2)] ### 중앙값 계산
avg4=max(N_list)-min(N_list) ### 최대값 - 최솟값

cnt=[0]*N ### 정수 개수 리스트 생성

for i in range(N):
    cnt[i] = N_list.count(N_list[i])   ### 정수 개수 리스트 생성

maxcnt=max(cnt) ### 최빈값의 원소 개수

if max(cnt)!=cnt.count(maxcnt):
    for _ in range(maxcnt):
        maxcntindex=cnt.index(maxcnt)
        N_list.remove(N_list[maxcntindex])   ### 최빈값이 여러개일경우 가장 작은 최빈값 제외

maxcntindex=cnt.index(maxcnt)
avg3 = N_list[maxcntindex]  ### 최빈값


print(avg1)
print(avg2)
print(avg3)
print(avg4)

shjohw12 1년 전 1

for i in range(N):

cnt[i] = N_list.count(N_list[i]) ### 정수 개수 리스트 생성

이 부분의 시간 복잡도가 어떻게 될지 생각해보세요

chldn323 1년 전 1

max, min, sum, count, index, remove 같은 함수들은 모두 O(n)의 시간 복잡도를 갖습니다.

평균, 최대, 최소는 이 함수를 쓰지 않아도 O(1)로 구할 수 있습니다.

가장 오래 걸리는 부분은 최빈값 부분인데 for문 안에 index+remove가 들어가면서 2중 for문 처럼 됐고 for문 하나로 줄여주면 됩니다.

mechauk 1년 전 0

감사합니다. 시간복잡도를 더 공부해야겠네요.

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

문제

문제

출처

ICPC

파이썬 시간초과 에러

mechauk 1년 전 0

shjohw12 1년 전 1

chldn323 1년 전 1

mechauk 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말