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

문제

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

풀이

처음 문제를 접했을 땐 '간단한 스택 구현 문제겠다~' 싶었으나..
예제를 보고 잠시 뇌정지가 왔읍니다..
그래도 stack의 특성을 알고 있으면 이해하는 데 그렇게 오래 걸리진 않을 문제이기 때문에 이해부터 하고 갑시다.

• 1부터 n까지의 수를 이용
• 위 수를 이용해 임의의 수열을 입력
• 입력된 수를 이용해 수열 만들기
  • 만들 수 있으면 push(+), pop(-) 과정 출력
  • 만들 수 없으면 "NO" 출력

문제에 주어진 조건을 정리하고 예제를 해석해봅시다.

예제 입력 1

8 # 1부터 8까지의 수
4
3
6
8
7
5
2
1

먼저 [1, 2, 3, 4, 5, 6, 7, 8] 이 수열을 push와 pop 연산을 통해 [4, 3, 6, 8, 7, 5, 2, 1] 이 수열을 만들 수 있는 지 확인해 보죠

뒤에 위치한 stack은 결과 stack입니다.

[] 1(push) []
[1] 2(push) []
[1, 2] 3(push) []
[1, 2, 3] 4(push) []
[1, 2, 3, 4] []

우리가 만들고자 하는 수열이 4로 시작하기 때문에 여기서 pop을 수행해서 결과 stack에 넣어줍시다.

[1, 2, 3] 4(pop) [4]

다음은 3이기 때문에 여기서 한 번 더 pop

[1, 2] 3(pop) [4, 3]

이 과정을 계속해서 수행해보겠습니다.

[1, 2, 5] 5(push) [4, 3]
[1, 2, 5, 6] 6(push) [4, 3]
[1, 2, 5] 6(pop) [4, 3, 6]
[1, 2, 5, 7] 7(push) [4, 3, 6]
[1, 2, 5, 7, 8] 8(push) [4, 3, 6]
[1, 2, 5, 7] 8(pop) [4, 3, 6, 8]
[1, 2, 5] 7(pop) [4, 3, 6, 8, 7]
[1, 2] 5(pop) [4, 3, 6, 8, 7, 5]
[1] 2(pop) [4, 3, 6, 8, 7, 5, 2]
[] 1(pop) [4, 3, 6, 8, 7, 5, 2, 1]

결과가 예제 입력과 동일하게 나온 것을 확인할 수 있습니다.

이제 예제 2번을 봐볼까요?

예제 입력 2

5
1
2
5
3
4

[] 1(push) []
[] 1(pop) [1]
[2] 2(push) [1]
[] 2(pop) [1, 2]
[3] 3(push) [1, 2]
[3, 4] 4(push) [1, 2]
[3, 4, 5] 5(push) [1, 2]
[3, 4] 5(pop) [1, 2, 5]

이제 여기서 3이 들어가야 하는데 이런..
앞에 stack의 끝에 4가 있네요.
그럼 예제 2번에 있는 수열은 만들어질 수가 없기 때문에 "NO"가 출력되어야 합니다.

이제 이를 코드로 작성하면 됩니다.

코드 및 해설

import sys
input = sys.stdin.readline

stk = [] # 앞 stack
res = [] # 결과
num = 1 # 현재 넣을 숫자

for _ in range(int(input())):
    n = int(input()) # 입력할 숫자
    
    while num <= n: # 입력하는 숫자가 현재 숫자 보다 크다면
        stk.append(num) # 숫자를 stack에 추가
        res.append('+') # 연산 과정을 결과 stack에 추가
        num += 1 # 현재 넣을 숫자 증가
    
    if n == stk[-1]: # stack에 있는 마지막 숫자가 현재 입력한 숫자와 같다면
        stk.pop() # pop 연산 수행
        res.append('-') # 연산 과정을 결과 stack에 추가
    else: # 마지막 숫자가 다르다면
        res.clear() # 결과 stack 초기화
        res.append('NO') # NO 추가
        break # 반복문 정지

for i in res:
    print(i) # 결과 출력