[백준 알고리즘: python 3] #1874 - 스택 수열 (스택 스터디)

알고리즘 스터디의 이번 주차는 스택/큐/덱을 공부하기로 했고, 이번 포스트는 스택 문제 중, 1874번 스택 수열 문제를 풀기로 했습니다.

---

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

 

 

1874번 스택 수열 문제는 백준 알고리즘 단계별 문제 중, 스택(Stack) 단계에 있는 문제입니다. 알고리즘 스터디에서 자료구조에 대해서 같이 공부를 하며 진행을 하자고 얘기가 됐고, 좋은 것 같아서 차근차근 단계별로 있는 자료구조 문제 세트를 풀기로 했어요. 문제의 선정 기준은 제출한 횟수가 많은 문제 중, 정답률이 제일 낮은 문제로 결정했네요.

 

당연한 말이지만, 스택 수열은 스택이라는 자료 구조를 활용하여 풀 수 있는 문제입니다. 스택이란 간단히, 입구가 하나인 통에 정보를 넣고 꺼낼 수 있는 자료 구조라고 할 수 있습니다. 비유를 하자면 과자 프링글스 같은 구조라고 할 수 있습니다. 처음 넣는 감자칩이 가장 아래에 들어가고 꺼내 먹을 때는 가장 위의 감자칩을 집게 되는 것처럼, 먼저 넣은 정보는 제일 아래에 들어가고(push) 정보를 꺼낼 땐 제일 마지막에 들어온 데이터를 꺼내게 되는 것(pop)이죠. 그래서 스택은 제일 마지막에 들어온 데이터가 제일 먼저 나간다는 의미에서 Last In First Out(LIFO) 이라고도 부른답니다.

맛있겠다..

 

Hint!

스택 수열 문제를 풀 때는 이 스택의 push와 pop기능을 잘 사용해야 하고, 정답률에 비해서는 그렇게 어렵지 않았습니다. python의 list는 스택이라는 것을 알고나 있는 듯이, list 메소드인 pop과 append를 제공합니다. pop은 스택에서 불리는 pop과 같은 의미로 리스트의 가장 마지막 요소를 빼내는 메소드이고, append는 스택에서 불리는 push와 같은 의미로 리스트의 가장 마지막 요소에 정보를 추가하는 메소드입니다. 그래서 따로 스택과 함수를 구현할 필요는 없이 list와 pop, append를 잘 활용하시기만 하면 됩니다.

 

간단하게 풀이를 설명하면,

1. 만들어야 하는 수열의 리스트(num_list), 수열의 길이(n) 만큼의 1부터 시작하는 연속된 자연수로 이루어진 리스트(one_to_n), 스택의 현재 상태를 나타내는 리스트(stack), 스택에서 pop, push의 여부를 기록하는 리스트(progress)를 먼저 만들어 둡니다. 
2. num_list에 수가 없을 때까지 아래 loop를 실행합니다.
   1. 먼저, stack에 넣을 one_to_n의 숫자가 없는데 stack의 마지막 숫자가 num_list의 첫번째 숫자와 같지도 않아서 빼낼 숫자도 없다면 그건 만들 수 없는 수열입니다. 한 마디로 할 수 있는 행동이 없는 것이죠. 이 땐 루프를 중단시키고 답으로 NO을 기록합니다.
   2. stack이 비어있다면, one_to_n의 첫번째 숫자를 빼내 stack에 append(push)합니다. progress 리스트에 "+"를 append합니다.
   3. stack의 마지막 숫자(맨 위 숫자)가 num_list의 첫번째 숫자와 같다면, stack과 num_list에서 그 숫자를 빼내고(pop) progress 리스트에 "-"를 append 합니다.
   4. 같지 않다면, one_to_n의 첫번째 숫자를 빼내 stack에 넣습니다. progress 리스트에 "+"를 append합니다.
3. progress를 출력합니다.

시간 초과가 날까 걱정하면서 제출을 했는데 다행히 연산이 그렇게 많진 않아서 (많아봐야 20만번인가요?) 가볍게 accept 받았네요 ! 아래의 코드로 통과하였습니다.

 

import sys

n = int(sys.stdin.readline())
num_list = []
for _ in range(n): num_list.append(int(sys.stdin.readline()))

stack = []
progress = []
one_to_n = [i for i in range(1, n+1)]
while num_list:
    # 할 수 있는 행동이 없으면 만들 수 없는 수열임.
    if not one_to_n and stack[-1] != num_list[0]:
        progress = ["NO"]
        break

    # 스택이 비어있으면 다음 숫자를 넣기
    if not stack:
        stack.append(one_to_n.pop(0))
        progress.append("+")
    
    # 스택에 있는 마지막 숫자가 만들어야 할 수열의 첫번째 숫자와 같다면
    if stack[-1] == num_list[0]:
        # 스택과 만들 수열의 첫번째 숫자를 빼내기(삭제)
        stack.pop()
        progress.append("-")
        num_list.pop(0)
    # 그렇지 않으면
    else:
        # 스택에 다음 숫자를 넣기
        stack.append(one_to_n.pop(0))
        progress.append("+")

    
for i in progress: sys.stdout.write(str(i)+'\n')