[BOJ] 1874 스택수열 (Python / 파이썬)

🧷 문제

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

1부터 n까지의 수를 스택에 넣고 빼는 것을 반복하는데, 오름차순으로만 push할 수 있고 임의의 수열이 주어졌을 때 위의 스택을 이용하여 만들 수 있는지 없는지를 알아보는 문제이다.

🛠 풀이

이 문제를 풀 때 처음에는 문제 자체를 이해하는데 어려움이 있었지만 아래에 있는 예제를 직접 손으로 그려가면서 이해할 수 있었다.

Step 1.
 1부터 n까지의 수를 넣어줄 sequence리스트와 결과로 보여줄 res리스트를 만들었다.
 그리고 num변수를 1로 초기화하고 문제 조건과 비교할 수 있는 check변수를 True로 설정한 후에 임의의 수열을 만들 수 없다면 NO를 출력할 수 있도록 만들었다.

Step 2.
 n개의 줄을 통해 입력되는 임의의 수열의 원소들을 tmp라는 이름의 변수로 받아주었다.
 while문을 이용해 num이 tmp보다 작거나 같을 때 sequence리스트에 num값을 push했다.
 동시에 결과로 보여줄 res리스트에는 +를 append해줬다.
 그 후에는 num값을 하나 올려주고 다시 비교해주었다.

Step 3.
 다음으로 sequence리스트의 top, 즉 sequence[-1]이 입력된 tmp값과 같다면 sequence리스트에서 pop을 해주고 동시에 res리스트에는 -를 append해준다.
 만약 sequencd[-1]이 tmp와 다르다면 문제에서 주어진 임의의 수열을 만들 수 없기 때문에 check를 False로 초기화 해준 후에 break로 for문을 빠져나가도록 하였다.

Step 4.
 성공적으로 for문을 다 돌았다면 check가 True일 것이고 이 경우에는 res리스트의 원소들을 하나씩 출력해준다.
 그렇지 않다면, check가 False일 것이고 이 때는 NO를 출력해준다.

🖊 나의 코드

import sys

if __name__ == "__main__":
    n = int(input())
    sequence = []
    res = []
    num = 1
    check = True
    for _ in range(n):
        tmp = int(input())
        while num <= tmp:
            sequence.append(num)
            res.append('+')
            num += 1
        if sequence[-1] == tmp:
            sequence.pop()
            res.append('-')
        else:
            check = False
            break

    if check:
        for r in res:
            print(r)
    else:
        print("NO")