📘[1874] 백준 스택 수열 풀이 및 참고자료(Python)

스택(Stack)이란?

스택은 나중에 들어온 요소가 먼저 나가는 형식인 LIFO(Last In First Out)의 성질을 갖는 선형 자료 구조이다.
파이썬에서는 리스트를 생각할 수 있다.
리스트는 append()와 pop()의 2가지 연산이 가능하다.
둘 다 가장 뒤에 요소를 추가, 추출하는 함수로, 맨 뒤에서만 연산이 이루어진다.
쉽게 생각하면 입출구가 하나 뿐인 방이라고 생각할 수 있다.

백준 스택수열

문제: https://www.acmicpc.net/problem/1874
스택수열 문제는 스택이 2개가 필요하다.
먼저, ‘+’, ‘-‘를 저장할 result 스택이 필요하고, 실제로 값이 들어갔다 나가는 용도의 스택인 stack 필요하다.

코드

import sys

n = int(sys.stdin.readline())

stack = []
result = []
find = True
count = 1

for i in range(n):
    num = int(sys.stdin.readline())
    while count <= num:
        stack.append(count)
        result.append('+')
        count+=1
    
    if stack[-1] == num:
        stack.pop()
        result.append('-')
    else:
        find = False

if not find:
    print('NO')
else:
    for i in result:
        print(i)

코드 분석

num에 stack[]에 들어갈 수가 입력된다.
그 수만큼 while문이 동작하도록 미리 설정해둔 count=1을 활용한다.
count는 반복할 수록 count+=1을 하여 증가시켜주고, 이 count는 반복문이 끝나면 결국 num이랑 같은 크기의 수가 된다.
이 count를 stack[]에 추가하고, 반복할 때마다 ‘+’를 result[]에 추가한다.
만약, stack[]의 가장 마지막 수가 num과 같다면, stack[]에서 pop()연산을 실행하고 result에 ‘-‘를 추가한다.
그게 아니라면, find=False를 설정하여 후에 “NO”를 출력하도록 한다.

위 동작이 끝나면 find=True일 경우에 대해 result를 차례대로 출력해주면 된다.

참고자료

https://hongcoding.tistory.com/39
https://data-flower.tistory.com/98