[Python][백준/BOJ] 1874번 : 스택 수열

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

1874번: 스택 수열

 

내 코드

import sys
input = sys.stdin.readline

n =int(input())
stack =[]
now =1
ans = []
flag =0
for i in range(1, n+1):
    dst = int(input().rstrip())
    
    while now <= dst:
        stack.append(now)
        now+=1
        ans.append('+')
    if stack[-1] == dst:
        stack.pop()
        ans.append('-')
    else:
        flag =1
        break    
    
if flag ==0:
    print('\n'.join(ans))
else:
    print('NO')

 

코드 리뷰

스택(LIFO)

스택은 제일 먼저 들어간 데이터가, 가장 먼저 나오는 LAST IN FIRST OUT 구조이다.

그래서 이 문제는 STACK 의 기본 개념을 이해하기에 좋은 문제가 아닐까 싶다.

문제에서 요구하는 것은 "STACK의 기본 개념을 이용하면서 진행하되, 스택에서 일어날 수 없는 상황은 break를 걸어라"이다.

for i in range(1, n+1):
    dst = int(input().rstrip())
    
    while now <= dst:
        stack.append(now)
        now+=1
        ans.append('+')
    if stack[-1] == dst:
        stack.pop()
        ans.append('-')
    else:
        flag =1
        break

1부터 n까지가 차례대로 들어갈 수 있는 수열이기 때문에 n번 돌리며 진행할 것이다.

먼저 stack의 수를 넣고 빼는 기준이 되는 dst 변수를 하나 입력받는다. 이 변수를 목적지라고 생각하고 풀었기 때문에 '목적 수'라고 부를 것이다.

 

만약 목적 수가 현재의 수보다 더 큰 수라면 오히려 좋다. 목적 수에 다다를 때까지 계속해서 now를 +1씩 올려준다. 이 때 중요한 것은 목적 수와 같아질 때까지 while문을 돌린다는 것이다.

now	시작 : 1	2	3	4	5
dst	입력 : 4
if stack[-1] == dst:				O

이렇게 일어날 수 있는 이유는, 문장 순서의 차이때문에 가능하다.

    while now <= dst:
        stack.append(now)
        now+=1

stack이라는 리스트 안에 now 수를 추가한 후, now를 하나 더 높여준다. 그래서 만약 now는 5라고 하더라도 stack 안에 있는 수는 4까지밖에 없는 것이다.

그리고 코드 안에는 now를 줄이는 코드는 존재하지 않는다. 이유는 'NO'를 출력하기 위해서이다.

스택 LAST IN FIRST OUT

해당 문제에서 요구하는 것은 앞에서 말했다시피, 스택의 본질인 LIFO를 사용하는 것 자체이다. 그래서 STACK을 봤을 때 가장 위에 있는 수(now)가 무조건 dst와 같거나, 작아야 한다.

만약 stack의 정말 깊숙이 숨어있는 작은 수가 있을 때, 스택이라는 리스트를 이리저리 헤집어서 안의 수만 쏙 꺼낼 수가 없다.

그저 쌓여있는대로 꺼낼 수 있을 뿐이다. 그러려면 STACK[-1]만 꺼낼 수 있다는 말이 되고, 결국 이게 목적 수와 같을 때만 뺼 수 있다는 것과 같다.

스택의 본질을 다시 생각하기에 좋은 문제였다.