글 읽기 - 시간 초과가 뜨네요ㅠ 도와줘요

hsinh 4년 전 0

문자열을 받습니다.

for로 돌면서 count()로 문자열이 몇번 쓰였나 체크해줍니다.

최고 기록 경신은 기록합니다.

최고 기록이 같으나 문자가 다르면 물음표를 던집니다.

그리고 출력하는 코드입니다.

..근데 시간초과 뜨네요... pypy로도 그렇군요

도와주세요..

s = input().lower()
k = 0
sc = 0
c = ''
for i in s:
    sc = s.count(i)
    if k<sc:
        k = sc
        c = i
    elif k==sc and c!=i:
        c = '?'
    
print(c.upper())

djm03178 4년 전 0

제목과 본문이 다르네요. 시간 초과인가요, 런타임 에러인가요?

nahwasa 4년 전 1

이 문제의 경우 O(N)으로도 가능하고, 약간 비효율적이라도, 최대로 쳐봐야 O(26N)으로 가능합니다. 하지만 올리신 풀이는 O(N^2)이 걸립니다.
물론 입력 길이가 작을 경우엔 올려두신 풀이도 효율적이지만 일반적으로는 더 오래걸립니다.

제목은 시간초과고 내용은 런타임이라 하셔서 헷갈리지만 뭐 어쨌든 시간초과는 확실해보입니다. 입력이 100만개라서요..
count 함수 자체가 반복문 하나가 더 들어가는걸 생각하셔야합니다.

즉 2중 반복문으로 푸신거고, 동일한 프로세스를 매우 여러번 반복하게 됩니다.

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

문제

문제

출처

ICPC

시간 초과가 뜨네요ㅠ 도와줘요

hsinh 4년 전 0

djm03178 4년 전 0

nahwasa 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말