[Python - Stack] 1874 스택 수열

📌 문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

📌 입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

📌 출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

📌 문제 풀이

👨‍🏫 접근

문제부터가 이해가 잘 되지 않았었다.

그래서 곰곰히 생각해보며 문제를 이해해보도록 했다.

먼저 예제 1을 분석해보자면,

8
4
3
6
8
7
5
2
1

먼저 1부터 8까지의 수가 있다.

 

첫 번째 수 4를 얻기 위해 1, 2, 3, 4를 push한다(++++). 이후 4를 얻기 위해 pop한다(-).

 

두 번째 수 3을 얻기 위해 pop한다(-).

 

세 번째 수 6을 얻기 위해 5, 6을 push한다(++). 이후 6을 얻기 위해 pop한다(-).

 

네 번째 수 8을 얻기 위해 7, 8을 push한다(++). 이후 8을 얻기 위해 pop한다(-).

 

나머지 수를 위해 계속해서 pop한다(----).

 

그래서 총 ++++--++-++-----라는 결과를 갖게 되는 것이다.

 

그 다음 예제 2도 분석했을 때,

5
1
2
5
3
4

첫 번째 수 1을 얻기 위해 1을 push한다(+). 다시 pop한다(-).

두 번째 수 2를 얻기 위해 2를 push한다(+). 다시 pop한다(-).

세 번째 수 5을 얻기 위해 3, 4, 5를 push한다(+++). pop한다(-). 스택에는 [3, 4]가 남는다.

네 번째 수 3을 얻기 위해 pop을 두 번 한다(--). 스택은 비어 있다.

다섯 번째 수 4를 얻고자 하나, 스택이 비어있어 얻을 수 없다. 따라서 불가능하다("NO")

 

고민을 꽤 많이 하면서 풀었다. 여기서 힌트는 stack을 사용한다는 점과, 오름차순으로 수가 증가하는 과정을 갖는다는 것?

 

두 번째 줄부터 시작하는 수를 차례차례 검사하면서 문제를 푼다. 중요한 것은, 종료조건과 불가조건을 잘 구분해야 한다는 것이다.

👨‍🏫 문제 풀이

📄 전체 코드

from sys import stdin

n = int(stdin.readline())

stack = [1]
cnt = 1
ans = "+"

num = int(stdin.readline())

while cnt != n + 1:
    if not stack or stack[-1] < num:
        cnt += 1
        stack.append(cnt)
        ans += "+"
    elif stack[-1] == num:
        stack.pop()
        ans += "-"
        if cnt == n and not stack:
            break
        num = int(stdin.readline())
    else:
        print("NO")
        exit()

print("\n".join(ans))

이렇게 풀 수도 있지만, 아래와 같이 푸는 게 더 명확한 풀이일 것 같다.

import sys

input = sys.stdin.read


def sol1874():
    n, *nums = map(int, input().split())
    cur = 1
    st = []
    answer = []
    for num in nums:
        while cur <= num:
            st.append(cur)
            answer.append('+')
            cur += 1
        if st[-1] != num:
            answer = ['NO']
            break
        st.pop()
        answer.append('-')
    print('\n'.join(answer))


if __name__ == '__main__':
    sol1874()

출처: https://www.acmicpc.net/source/41973273

📄 준비

import sys

input = sys.stdin.read


def sol1874():
    n, *nums = map(int, input().split())
    cur = 1
    st = []
    answer = []

현재 진행 정도를 받기 위해 cur이라는 변수를, 스택을 위해 st라는 변수를, 답을 제출하기 위해 answer라는 변수를 설정한다.

📄 풀이

    for num in nums:
        while cur <= num:
            st.append(cur)
            answer.append('+')
            cur += 1
        if st[-1] != num:
            answer = ['NO']
            break
        st.pop()
        answer.append('-')
    print('\n'.join(answer))


if __name__ == '__main__':
    sol1874()

각 수들을 검사한다. 여기서 cur이 num보다 같거나 작을 동안 계속해서 수를 스택에 넣고, answer를 수정한다. cur이 num을 넘게 되면 그 이후로는 계속해서 pop을 해야 한다는 것이다.

 

예를 들어, num이 5이고, cur이 1일 때 계속해서 cur을 늘리고 st에 cur값을 push한다. 그러면 cur이 6이 되었을 때 비로소 while 반복문을 탈출하게 되며 stack은 [1, 2, 3, 4, 5], answer는 ["+", "+", "+", "+", "+"] 이렇게 되고, st의 -1 인덱스 값은 5이므로 if st[-1] != num을 만족하지 못하고 정상적으로 pop을 할 수 있게 된다.

 

그 다음 num이 3이라고 해보자. 그러면 cur은 6이기 때문에 바로 다음 단계로 넘어간다. 이때 st는 [1, 2, 3, 4] 인데, num은 3이므로 불가능한 조건이 된다. 왜냐하면 그 이후에 4가 등장한다고 했을 때, 이전에 3을 출력하기 위해 st를 [1, 2] 로 만들었기 때문에 어떻게 하든 4를 출력할 수 없다.

📌 총평

코테 실력이 많이 죽었다... 도메인 지식도 중요하지만 알고리즘 공부도 게을리 하지 말자!