[파이썬] 백준 1874 : 스택 수열

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

1874번: 스택 수열

실버 3

자료구조, 스택

 

[파이썬] 백준 1874 : 스택 수열

---

문제 접근을 잘못했고 구현하는데 어려움이 너무 많아 다른 사람 코드를 참고했음.

 

코드

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
stack = deque()
lst = []
cnt = 1
flag = True
for _ in range(n):
    num = int(input())
    while cnt <= num:
        lst.append(cnt)
        stack.append('+')
        cnt += 1
    if num == lst[-1]:
        lst.pop()
        stack.append('-')
    else:
        flag = False

if flag == False:
    print('NO')
else:
    for i in stack:
        print(i)

 

1 2 3 4 5 6 7 8을

4 3 6 8 7 5 2 1로 정렬하기

 

값을 입력하면 1~해당값 까지 lst에 삽입.

lst의 top값(가장 오른쪽 위치의 값)과 입력한 값과 같다면 pop을 한다.

 

4 3 6 8 7 5 2 1을 각각 입력받는 동안 pop이나 append를 수행하도록 한다.

 

 

예를 들어 4를 입력받으면 1~4까지 lst에 append 한다. 이때 1~4까지의 값을 기억하는 변수를 cnt로 설정한다.

lst의 top값인 4는 입력했던 4와 같은 값이므로 pop을 한다.

 

그다음 입력하는 3은 lst의 top값인 3과 같으므로 pop을 한다.

 

그다음 입력하는 6은 cnt보다 큰 값이므로, cnt~6까지 값을 lst에 append 한다.

 

이 과정을 반복해야 한다.

 

즉, append가 먼저 일어나고, 입력한 값과 lst의 top값이 같으면 pop을 하도록 구현해야 한다.

 

 

1 2 3 4 5를 1 2 5 3 4로 정렬해야 하는 경우를 생각해보자.

 

1 입력 -> 1을 append, pop

2 입력 -> 2를 append, pop

5 입력 -> 3, 4, 5 append, 5를 pop

3 입력 -> ... pop의 조건은 lst의 top값(가장 오른쪽 위치의 값)과 입력한 값과 같을 때 수행된다.

top이 4가 되었으므로 입력했던 값인 3과 서로 다르므로 pop을 수행할 수 없다.

따라서 이런 경우에 대해 NO를 출력하도록 구현하도록 해야 한다.

이는 Flag변수로 구분함으로써 반복문을 빠져나올 때 Flag의 값에 따라 stack에 저장된 값을 출력할지 No를 출력할지를 분기로 나누도록 했다.