글 읽기 - 파이썬 시간초과가 뜹니다

bsmbaek 3년 전 0

어떻게 시간을 줄일 수 있을까요

조언 부탁드립니다.

import sys
def judgment(n):
    if n in s:
        if n==s[-1]:
            s.pop()
            ans.append("-")
        else:
            ans.append("NO")
    elif n in k:
        s.append(k.pop())
        ans.append("+")
        judgment(n)
    else:
        ans.append("NO")
    
    

n = int(sys.stdin.readline())
a = list(int(sys.stdin.readline()) for _ in range(n))
k = [n-i for i in range(n)]
s=[]
ans = []



for i in a:
    judgment(i)

if 'NO' in ans:
    print("NO")
else:
    for l in range(len(ans)):
        print(ans[l])

pmn0001 3년 전 1

if n in s :

위 부분은 s안에 있는 모든 요소들을 확인하기 때문에 시간이 매우 오래걸릴 것 입니다.

마찬가지로 elif n in k : 부분도 k의 모든 요소를 확인하기 때문에 시간이 매우 오래 걸립니다.

10만개나 되는 요소를 담을 수 있기 때문에 위같은 방법으로 탐색하기에는 시간이 부족합니다.

스택의 성질을 조금 더 활용해보세요

스택에서 pop하면 뭐가 나오는지, 현재 내가 어떤 숫자까지 스택에 넣었는지를 고려해보세요

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

문제

문제

출처

ICPC

파이썬 시간초과가 뜹니다

bsmbaek 3년 전 0

pmn0001 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말