BAEKJOON 1874スタック数列

質問する

https://www.acmicpc.net/problem/1874

に答える

与えられた入力範囲が非常に大きいため、再帰的に呼び出して含むか含まないかを解く場合にタイムアウトが発生する可能性があります.
したがって,グリッド方式で1つずつ追加し,所与の数字と比較し,スタックから値を1つずつ減算し,所与の値と比較する方式が有効であると考えられる.

コード#コード#

import sys
sys.stdin = open('input.txt')
N = int(input())

lst = []
for _ in range(N):
    lst.append(int(input()))

cnt = 0                         # 숫자가 몇까지 들어갔는지 기록
result = []                     # 연산자를 담을 리스트
stack =[]                       # 실제 수를 담을 리스트
flag =1                         # 만약 수열을 완성할 수 없으면 flag를 -1로 바꾸어줌
for i in lst:
    if flag==-1:                # 수열을 완성할 수 없으면 반복 종료
        break
    if i > cnt:                 # 주어진 리스트의 값이 cnt 보다 크면
        while i != cnt:         # 리스트의 값과 cnt 가 같을 때까지 push 해주면서 cnt를 +1 해줌
            cnt+=1
            result +=['+']
            stack.append(cnt)
        stack.pop()             # cnt와 리스트의 값이 같으면 stack에서 pop해줌
        result+=['-']
    elif i < cnt:               # 만약 cnt보다 현재 리스트의 값이 작다면
        while True:             # stack의 pop 값이 리스트의 값과 같을 때가지 계속해서 pop
            result+=['-']
            if len(stack)==0:   # stack 의 크기가 0인데 아직도 리스트의 값과 같은게 나오지 않았다면
                flag = -1       # 수열을 완성할 수 없음으로 flag를 -1로 바꾸고 함수 종료
                break
            if stack.pop() == i:
                break
if flag == 1:
    for i in result:
        print(i)
else:
    print('NO')

結果

一度提出して合格したが、時間がきつい.実際のコード採点時間がかなり長いと思っていたので間違っていました.
時間を早く通過する人のコードから見ると、方法はあまり違いません.しかし、実施中に問題が発生したようだ.
どこが問題なのか分からないので、コードをもう少し分解すべきだと思います.