글 읽기 - 파이썬 시간초과 관련 질문드립니다

kgood1 4년 전 0

스택수열에 관해서 풀어본 소스코드입니다.

정답은 제대로 나오나 최적화 되지 않았는지 시간초과가 뜹니다

어느것이 안좋은지 조언 해주시면 감사하겠습니다

from collections import deque
import sys
input=sys.stdin.readline
n=int(input())
number=deque()
stack=deque()
ans=[]
NO=False
for i in range(1,n+1):
    number.append(i)
for i in range(n):
    a=int(input())
    while a in number:
        stack.append(number.popleft())
        ans.append('+')
    if stack[len(stack)-1]!=a:
        NO=True
    else:
        stack.pop()
        ans.append('-')
if NO:
    print('NO')
else:
    for i in range(len(ans)):
        print(ans[i])

djm03178 4년 전 1

deque에서 in을 하는 연산은 deque 전체를 순회해야 하기 때문에 한 번 연산에 O(N)의 시간이 걸립니다.

kgood1 4년 전 0

정말 감사해여 하나알아갑니다 ㅎ

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

문제

문제

출처

ICPC

파이썬 시간초과 관련 질문드립니다

kgood1 4년 전 0

djm03178 4년 전 1

kgood1 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말