글 읽기 - 5766 파이썬 시간초과 질문이요!

whdgurclzls 5년 전 0

안녕하세요!

배열 만개 만들고 하나씩 카운팅 하면 당연히 시간초과 뜰거같아서

a라는 배열에 자료 다 넣고 c라는 배열을 set처럼 만들어서(중복 없앤 자료) 카운팅 한 뒤 2위 찾아서 출력하는 코드를 짜보았는데요..

그래도 시간초과가 났습니다

저기 ##################### 로 표시해 둔 부분이 제일 의심스러운데 저 부분 시간을 줄일 수 있는 힌트 부탁드립니다

혹시나 저게 문제가 아니라면 다른곳 어느부분이 문제가 될거같은지 말해주시면 감사하겠습니다!

좋은하루 되세요 :)

from sys import*
input=stdin.readline

while 1:
    N,M=map(int,input().split())
    if N==0 and M==0 : break
    a=[]; c=[]; cnt=[]  #a->중복 자료, c-> set배열로, cnt->갯수, cnt_2->갯수자리
    ##############################
    for i in range(N):
        b=list(map(int,input().split()))
        for j in range(M):
            a.append(b[j])
            if b[j] not in c:
                c.append(b[j])
    ##############################
    c.sort()
    for i in range(len(c)):
        cnt.append(a.count(c[i]))
    cnt_2=cnt[:]
    cnt.sort(reverse=True)
    max=cnt[0]
    for i in range(1,len(cnt)):
        if max != cnt[i]:
            second = i
            break
    temp=0
    temp_last=cnt.count(cnt[second])
    for i in range(len(cnt_2)):
        if cnt_2[i] == cnt[second]:
            print(c[i],end=' ')
            temp+=1
            if temp == temp_last:break
    print()
    

k5nen 5년 전 1

13행의 not in 연산자는 list를 대상으로 탐색하면 평균 O(N)의 시간복잡도를 가집니다.

이 문제는 처음에 생각하신 대로 10000 크기의 배열을 만들고 하나씩 세어도 풀 수 있습니다.

whdgurclzls 5년 전 0

그렇군요!

시간내어 답변해 주셔서 감사합니다!

좋은 하루 되세요 :)

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

문제

문제

출처

ICPC

5766 파이썬 시간초과 질문이요!

whdgurclzls 5년 전 0

k5nen 5년 전 1

whdgurclzls 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말