글 읽기 - 어느 부분에서 시간초과가 발생하게 되는지 잘 모르겠습니다 ㅠㅠ

donny0417 1년 전 0

짐작하기로는 최빈값을 구할 때 for문을 많이 사용해서 그런가 싶기도 한데...

어느 부분 때문에 시간 초과가 발생하는지,

또 어떻게 해결을 해야할지 잘 모르겠습니다 ㅠㅠ

도와주시면 감사하겠습니다!!

import sys

n = int(sys.stdin.readline().strip())

lst = []

for i in range(n):
    a = int(sys.stdin.readline().strip())
    lst.append(a)

lst.sort()

tot = 0

for j in lst:
    tot += j

#산술 평균
print(int(round(tot/len(lst),0)))

#중앙값
mid = int((len(lst)-1)/2)

if len(lst) % 2 == 0:
    print((lst[mid]+lst[mid+1])/2)
else:
    print(lst[mid])

#최빈값
num = []
mode = []

for k in lst:
    num.append(lst.count(k))

for l in range(len(num)):
    if num[l] == max(num):
        mode.append(lst[l])

if len(mode)>1:
    mode.remove(min(mode))
    print(min(mode))
else:
    print(min(mode))

#범위
print(max(lst)-min(lst))

djm03178 1년 전 0

리스트에서 count를 하는 것은 그 리스트 전체를 보면서 하나씩 개수를 세는 것입니다. 이를 모든 원소에 대해 진행하고 있으니 길이의 제곱에 비례하는 시간이 걸립니다. 더 빠르게 수를 세야 합니다.

donny0417 1년 전 0

하나씩 세는 방법이 아니라면 어떤 방법이 있나요??

djm03178 1년 전 0

하나씩만 세면 괜찮은데 이 코드는 그걸 모든 원소에 대해서 전부 개별적으로 전체 리스트를 보면서 세고 있기 때문에 문제가 됩니다. 리스트를 딱 한 번만 순회해도 각 수가 등장하는 개수를 전부 세면서 진행할 수 있습니다.

donny0417 1년 전 1

최빈값 부분 수정해서 채점을 받으려고 했는데 런타임에러(NameError)가 발생했습니다

이번에는 어떤 부분이 문제가 되는지 잘 모르겠습니다...

그리고 전부 개별적으로 리스트를 보면서 세고 있는게 문제라고 하셔서 하나씩만 세는거로 바꿔본다고 했는데 말씀해주신 것이 의도하는 바와 다른 것 같습니다...

리스트를 한 번만 순회해도 각 수가 등장하는 개수를 전부 셀 수 있다고 해주셨는데 그 방법을 잘 모르겠습니다...

코드 형태로 예시를 보여주시면 감사하겠습니다!!

import sys

n = int(sys.stdin.readline().strip())

lst = []

for i in range(n):
    a = int(sys.stdin.readline().strip())
    lst.append(a)

lst.sort()

#산술 평균
tot = 0

for j in lst:
    tot += j


print(int(round(tot/len(lst),0)))

#중앙값
mid = int((len(lst)-1)/2)

if len(lst) % 2 == 0:
    print((lst[mid]+lst[mid+1])/2)
else:
    print(lst[mid])

#최빈값
num = list(set(lst))
cnt = []
mode = []

for i in num:
    a = 0
    for j in lst:
        if i == j:
            a+=1
    cnt.append(a)

b = max(cnt)

for i in range(len(cnt)):
    if cnt[i] == b:
        mode.append(num[i])

if len(mode)>1:
    mode.remove(min(mode))
    print(min(mode))
else:
    print(min(mode))
    
#범위
print(max(lst)-min(lst))

djm03178 1년 전 1

https://yeowool0217.tistory.co... 를 참고해 보세요.

donny0417 1년 전 0

도와주신 덕에 해결할 수 있었습니다!!

딕셔너리를 활용하는 법을 새롭게 배우게 되었네요

답변 감사드립니다~~

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

문제

문제

출처

ICPC

어느 부분에서 시간초과가 발생하게 되는지 잘 모르겠습니다 ㅠㅠ

donny0417 1년 전 0

djm03178 1년 전 0

donny0417 1년 전 0

djm03178 1년 전 0

donny0417 1년 전 1

djm03178 1년 전 1

donny0417 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말