글 읽기 - 1874 python 시간초과 한마디 조언 부탁드립니다

zmfpdl64 1년 전 0

시간초과가 발생하는데 O(N^2)연산을 해서 그런걸까요?

소중한 한마디 부탁드립니다

n = int(input())
vi_map = deque([True]*(n+1))
a = []  #문제 pop 배열들
stack = deque()
stack2 = deque()
answer = ""
for i in range(n):
    a.append(int(sys.stdin.readline().rstrip()))
for i in a:
    for j in range(1,i+1):
        if vi_map[j] == True:   
            vi_map[j] = False
            stack2.append("+")
            stack.append(j)
    if len(stack) != 0 and stack[-1] == i:
        stack.pop()
        stack2.append("-")
    else:
        answer = "NO"
        break
if len(answer) != 0:
    print(answer)
else:
    for i in stack2:
        print(i)

zenith82114 1년 전 1

네. N 10만에 시간제한 2초면 O(N^2) 알고리즘은 거의 확정적으로 시간초과가 납니다.

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

문제

문제

출처

ICPC

1874 python 시간초과 한마디 조언 부탁드립니다

zmfpdl64 1년 전 0

zenith82114 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말