백준 - 1874번 스택 수열

문제링크: https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

차근차근 알고리즘을 연습해보려고 가장 기본적인 스택부터 시작했다.

문제 설명

먼저 간단히 문제 설명을 하자면(처음에 문제 이해를 잘못해서 뭐지? 싶었다,,,)

입력으로 주어진 수열을 스택을 이용해 만드려고 하는데, 스택에는 오름차순으로만 push될 수 있다.

이러한 조건을 이용해서 수열을 만들 수 있으면 push와 pop한 기록을 출력하고, 만들 수 없다면 "NO"를 출력하는 프로그램을 구현하는 것이다.

 

알고리즘 설명

(입력받는 과정은 생략)
1. 1부터 n까지 for문을 돌며 stack에 push한다. push할 때 answer변수에 '+'를 append한다.
2. li의 현재 인덱스, 즉 현재 살펴보고 있는 수열의 수와 stack의 top값을 비교한다.
3-1. 만약 두 값이 같다면, 현재 살펴보고 있는 수열의 수와 stack의 top값이 다를 때까지 while문을 돌며 stack에서 pop을 한다. 이때, answer변수에 '-'을 append한다.또한, stack의 pop한 값을 answer_num변수에 append한다.
3-2. 만약 두 값이 다르다면, continue한다.
4. for문을 다 마치면 stack에 남아있는 수만큼 answer변수에 '-'을 append한다. 또한, stack의 pop한 값을 answer_num변수에 append한다.
5. answer_num과 li를 비교해 두 값이 같다면 answer값을 순차적으로 출력하고 두 값이 다르다면 "NO"를 출력한다.

 

코드

n = int(input())
li = [] # 입력을 받는 리스트
for i in range(n):
    li.append(int(input()))

stack = [] # 스택으로 사용할 리스트
answer = [] # '+'와 '-'를 저장할 리스트
answer_num = [] # li와 값을 비교할 리스트
current = 0 # 현재 li의 인덱스를 나타내는 변수

for i in range(1, n + 1):
    stack.append(i)
    answer.append('+')
    if li[current] == i:
        while stack and current < len(li) and li[current] == stack[-1]:
            answer_num.append(stack.pop())
            current += 1
            answer.append('-')

while stack:
    answer_num.append(stack.pop())
    answer.append('-')

if answer_num != li:
    print("NO")
else:
    for i in answer:
        print(i)