[Baekjoon] 1874 - 스택 수열 (Python)

문제

[BaekJoon] 1874 스택 수열

스택이라길래 별 거 없을 줄 알았는데 문제를 이해하는 데에 생각보다 오래걸렸다.

스택이 무엇인지 알고 있지만 스택의 응용을 완벽하게 이해하지 못하고 있었던 것 같고, 문제이해능력이 아직은 조금 부족한 것 같다. 이 부분은 꾸준히 문제를 풀면서 기르려고 노력하는 중이다.

결론은 이 문제는 1 ~ n 정수를 오름차순으로 스택에 적절히 push or pop 하면서 입력으로 주어진 순열을 만들면 되는 문제이다.

Input

정수 n 을 입력받는다. 그리고 n개의 원하는 data로 이루어진 수열을 입력한다.

Output

필요한 연산에 따라 push 는 '+', pop은 '-'로 나타내어 출력한다. 입력한 수열을 만들 수 없을 경우엔 “NO”를 출력한다.

풀이

입력을 항상 sys.stdin.readline() 일일이 다 썼었는데 다른 블로그에서 좋은 방법을 보게 되어 input = sys.stdin.readline 으로 저장해놓고 실제 입력받을 때는 n = input() 이런 식으로 좀 더 짧게 방법을 바꿨다.

코딩 테스트 에서는 대부분 입력이 한 줄로만 끝나지 않아서 2~3번 쓰는 것 보다는 더 좋은 방법인 것 같다.

정수 n을 입력받고 나서, n이하로 n개의 정수data를 입력한다.

첫 번째로, 만들고자 하는 수열의 맨 앞 숫자 이하의 수는 stack에 push해야한다. 그러기 위해 cnt = 1 의 변수를 만들었다. 처음에는 num = [i for i in range(1, n+1)]과 같은 방식으로 아예 n까지의 리스트를 만들어놨었는데 해결방법이 떠오르지 않았었다.

아무튼 cnt가 목표 수열 맨 앞 숫자와 같아질 때 까지 cnt를 1씩 증가시키면서 stack에 더해준다.

그리고 입력 data가 stack의 top 숫자와 같다면 pop하여 수열을 만들어 나가면 끝이다.

Code

import sys
input = sys.stdin.readline

n = int(input())

posb = True
op = []
stack = []
cnt = 1

for _ in range(n):
    data = int(input())

    # data(입력 숫자) 이하까지 stack에 push
    while cnt <= data:
        stack.append(cnt)
        op.append('+')
        cnt += 1
    
    # stack의 top과 data(입력 숫자)가 같다면 pop
    if stack[-1] == data:
        stack.pop()
        op.append('-')

    else:
        posb = False # 수열 생성 불가능
        break
# output
if posb == False:
    print("NO")
else:
    for i in op:
        print(i)