[Baekjoon] 1874번 : 스택 수열 (Python)

Python

방법 1 - 메모리 32424KB / 시간 5752ms / 코드 길이 357B

스택을 활용한 문제이다.

스택을 추가할 때는 list로 append 뺄 때는 pop을 사용한다.

이에 대한 기본 내용을 숙지하고 문제에 들어간다.

아래 풀이는 stack list와 + 혹은 - 를 기입하는 정답 list 2개만을 활용하여 사용한다.

문제의 특징상 오름차순인 1~n까지의 숫자를 차례대로 스택에 넣고 각 숫자를 넣을 때마다 원하는 리스트 값과 같은지를 확인한다. 단, 본 코드에서는 원하는 리스트 값이라 하는 것이 list의 형태가 아니라 num이라는 숫자로 개별값으로 얻는다.

만약 스택의 마지막 값과 정답과 다르다면 바로 break를 통해 종료하고 NO를 적으며 그렇지 않다면 stack의 값을 빼고 ans list에 '-'를 넣는다.

stack = []
ans = []
flg = 0
cnt = 0

for i in range(int(input())):
    num = int(input())

    while cnt < num:
        cnt += 1
        stack.append(cnt)
        ans.append('+')

    if stack[-1] == num:
        stack.pop()
        ans.append('-')
    else:
        print('NO')
        flg = 1
        break

if flg == 0:
    for i in ans:
        print(i)

방법 2 - 메모리 36672KB / 시간 144ms / 코드 길이 414B

3개의 list를 기반으로 문제를 푸는 방식이다.

우리가 스택의 pop을 통해 만들고자 하는 target list

1~n까지의 숫자를 차례대로 stack에 넣고 target list를 구성하고자 하는 stack list

stack list의 pop과 append에 따라 '+'와 '-'를 구성하고자 하는 answer list

이 3개의 리스트를 기반으로 결과값을 도출한다.

import sys
input = sys.stdin.readline

n = int(input())
targets = [int(input()) for _ in range(n)]
current = 1
stack, answer = [], []

for target in targets:
    while current <= target:
        stack.append(current)
        answer.append('+')
        current += 1

    if stack[-1] == target:
        answer.append('-')
        stack.pop()
    else:
        answer = ['NO']
        break

print('\n'.join(answer))