[ 알고리즘 ] 백준 1874 - 스택 수열

문제 링크 : link 

문제 티어 : 실버2

1874번: 스택 수열

---

---

아이디어

 

1. 입력된 값이 현재 stack의 top보다 크거나 같다면, 입력된 최댓값을 cur이라 할 때 (n - cur)만큼 push한 뒤, 입력된 값을 pop해야 한다. 

2. 그러다가 입력된 값이 top보다 작다면 잘못된 거다. 왜냐하면 top에 있는 값을 push하지 않고 pop을 할 수 없기 때문에 순서가 꼬인 것.

3. 풀다가 지인의 설명으로 알게 된 건데, NO만 출력하게 하기 위해선 answer를 저장하기 위한 리스트에 문자열을 넣은 뒤, 문제가 안 생긴다면 answer를 순서대로, 문제가 생긴다면 NO를 출력한다.

---

코드

import sys

def main():
    N = int(input())
    stack = []
    ans = []
    cur = 0
    flag = 0
    for _ in range(N):
        n = int(sys.stdin.readline().strip())
        if not stack or stack[-1] <= n:
            for j in range(n - cur):
                stack.append(cur + j + 1)
                ans.append('+')
            stack.pop()
            ans.append('-')
            if n > cur:
                cur = n
        elif stack[-1] > n:
            flag = 1
            break

    if flag:
        print('NO')
    else:
        print('\n'.join(ans))

if __name__ == '__main__':
    main()