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

(追記) (追記ここまで)

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

5766번 - 할아버지는 유명해!

whdgurclzls 7년 전 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 7년 전 1

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

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

whdgurclzls 7년 전 0

그렇군요!

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

좋은 하루 되세요 :)

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

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

whdgurclzls 7년 전 0

k5nen 7년 전 1

whdgurclzls 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말