앎을 경계하기

Programming/Algorithm

백준 #1874 - 스택 수열 python

양갱맨 2019. 10. 20. 01:52

처음 접근법 : 스택 두 개를 만들고 하나 스택은 push 하는 용도, 나머지는 pop 하는 용도 → 시간 초과, 메모리 초과

두번째 접근법 : 덱 하나에 push 했다가 pop한 숫자들 다시 덱에 넣어서 계속 검사하게 만듦 → 시간 초과

세번째 접근법 : 스택 하나에 입력된 수 만큼 넣었다가 top이 입력한 수와 맞으면 pop하도록 함 → 정답

import sys
import collections

n = int(sys.stdin.readline())
stack = collections.deque()
ans = ''
idx = 0
for i in range(n):
    num = int(input())
    while idx < num:
        if num >= idx:
            idx+=1  
            ans+='+\n'
            stack.append(idx)
    while stack and stack[-1] == num:
        ans+='-\n'
        stack.pop()
        continue
if not stack :
    print(ans.rstrip())
else:
    print("NO")
         

'Programming > Algorithm' 카테고리의 다른 글

백준 #13913 - 숨바꼭질4  (0) 2019.11.09
백준 #1697 - 숨바꼭질  (0) 2019.11.09
백준 #1021 - 회전하는 큐 python  (0) 2019.10.19
백준 #10828 - 덱 python  (0) 2019.10.19
백준 #11866 - 조세퍼스 문제 0 python  (0) 2019.10.19