글 읽기 - 시간 초과가 어디서 나는건가요 ?

johyesong8686 3년 전 0

어디서 시간 초과가 나는건가요 ?

아무리 봐도 시간 초과 날 구석이 없어보이는데..O(N)

t = input()
arr=[]

def check(str):
    if(str[::-1]==str): #회문인지 확인
        return 0
    else:
        result=False
        for i in range(len(str)): #유사회문 가능한지 확인
            changeStr=str[:i]+str[i+1:len(str)]
            if(changeStr ==changeStr[::-1]):
                result=True
                break;
        if result:
            return 1
        else :
            return 2
    
for _ in range(int(t)):
    x =input()
    print(check(x))

Green55 3년 전 1

str[:i]+str[i+1:len(str)] 와 (changeStr ==changeStr[::-1]) 모두 한번이 O(n)입니다.

johyesong8686 3년 전 0

@Green55

아 그렇군요 처음 알았네요 ㅠㅠ 감사합니다!!1

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

문제

문제

출처

ICPC

시간 초과가 어디서 나는건가요 ?

johyesong8686 3년 전 0

Green55 3년 전 1

johyesong8686 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말