[백준] 1874번. 스택 수열 (파이썬)

문제

문제 링크

처음에 문제를 읽었을 때는 "스택~ push~ pop~ 오키 알겠어" 였는데 문제를 이해하는데 생각보다 오래 걸렸지만 생각보다 간단했다!
1부터 입력으로 주어진 숫자(예를 들어 8)를 오름차순으로 스택에 push하면서 적절히 pop해 입력으로 주어진 수열 4, 3, 6, 8, 7, 5, 2, 1을 만들면 된다.

풀이

위의 그림과 같은 과정을 통해 스택으로 수열을 만든다.
1) 첫 번째 수인 4 이하인 수를 모두 스택에 넣는다. stack = [1, 2, 3, 4]
2) 스택의 가장 위 숫자와 첫 번째 수가 같으면 pop()으로 스택에서 꺼낸다. stack = [1 2]
3) 동일하지 않으면 스택 수열을 만들 수 없으므로 NO를 출력한다.

코드

github

count = 1
temp = True
stack = []
op = []

N = int(input())
for i in range(N):
    num = int(input())
    # num이하 숫자까지 스택에 넣기
    while count <= num:
        stack.append(count)
        op.append('+')
        count += 1

    # num이랑 스택 맨 위 숫자가 동일하다면 제거
    if stack[-1] == num:
        stack.pop()
        op.append('-')
    # 스택 수열을 만들 수 없으므로 NO
    else:
        temp = False
        break

# 스택 수열을 만들수 있는지 여부에 따라 출력 
if temp == False:
    print("NO")
else:
    for i in op:
        print(i)

stack은 오름차순으로 숫자를 넣은 스택
op는 push, pop여부에 따른 연산여부를 +, -로 저장한다.