백준 1874 스택 수열

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

복습하는김에 다시 한번 풀어보자

n = int(input())
arr = [i for i in range(1, n + 1)]
stack = []
res = []
tem = 0
for i in range(n):
    a = int(input())
    while tem < a:
        tem += 1
        stack.append(arr.pop(0))
        res.append("+")
        
    if stack[-1] == a:
        stack.pop()
        res.append("-")
    else:
        print("NO")
        exit(0)
    
for x in res:
    print(x)

풀이

stack을 이용하여 푸는 문제이다.

위의 예제를 예로 들어 설명하면, 처음으로 4를 입력했다.
즉, 내가 첫 번째로 pop한 숫자가 4가 되어야 한다. 그러기 위해서는 1,2,3,4가 이미 스택안에 있어야 한다.
그래서 입력한 수를 만날 때 까지는 계속 push를 해서 1,2,3,4가 스택에 있도록 해야한다.

1. 1, 2, 3, 4를 stack에 넣고 이 과정에서 res 리스트에 +를 추가한다

• 차례대로 꺼내야하기 때문에 tem의 값을 a와 비교하여 작다면 tem의 값을 +1 해주면서 stack에 append한것이다

2. stack의 맨끝이 꺼내려는 값 a와 같다면 빼주면서 res에 "-"를 추가한다.