백준 1874 - 스택 수열 (파이썬)

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

1874번: 스택 수열

 

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
pair = lambda : map(int, input().split())


n = int(input())
arr = [int(input()) for _ in range(n)]
dq = deque()
cnt = 0
res = ""

for i in arr:
    while 1:
        if cnt > n:
            print("NO")
            exit()
        if dq:
            if dq[-1] == i:
                dq.pop()
                res += "-"
                break
        cnt += 1
        dq.append(cnt)
        res += "+"

[print(i, end = '\n') for i in res]

 

문제를 제대로 이해하지 않은 상태에서 시작해서 시간이 오래 걸렸다.

 

파이썬에는 stack이 없으므로 deque를 이용하였다.

하지만 뒤에서만 pop, push가 일어나므로 list나 deque나 퍼포먼스는 동일할 것이다.

deque는 앞, 뒤에서의 pop, push가 빈번할 때 사용하는 자료구조이므로

덱을 사용할 때는 왜 이 구조가 필요한지 문제정의를 더 확실하게 할 필요가 있다.

 

 

문제의 핵심 아이디어는 "주어진 배열의 원소와 일치하는 값을 찾을 때까지 push, 찾았다면 pop" 이다.

 

따라서 주어진 배열의 원소를 반복 변수 i로 하는 for문을 두고,

마지막 값이 일치한다면 pop 하고 연산기호를 res에 기록해준 뒤 while문을 빠져나온다.

 

 

break를 하는 이유는,

원래 while문이 반복할 때마다 1씩 증가하는 cnt를 dq에 계속해서 push 해주는 역할인데,

이 push 전에는 i와 일치하는지 확인하는 과정인 if dq == i가 항상 우선되어야 하기 때문이다.

 

설명을 덧붙이자면

1,2,3,4가 push되고 4,3이 pop되는 과정에서 중간에 5가 추가된다거나 하는 일이 있어서는 안되고

pop 과정이 완전히 종료된 다음에 push가 이어져야 하기 때문에

pop 이후에 이어지는 push 과정으로 가지 않도록 break로 빠져나와주는 것이다.

 

 

또한 불가능한 경우의 처리도 해줘야 하는데

수열을 만들지 못하는 경우에는 pop이 이루어지지 않으며 무한히 push가 이어지기 때문에

단순히 push되는 값인 cnt가 n을 초과하는지 여부만 확인해주면 된다.

 

그리고 이 값을 출력할 때도 check값을 선언해서 NO와 res중 어느 것을 출력할지 결정하도록 해도 되지만

그냥 간단하게 exit()을 활용해도 된다.