[백준/Stack] 1874번 : 스택 수열

- 문제 : https://www.acmicpc.net/problem/1874

 

문제 자체를 이해하기 어려웠던 문제다.

 

블로그를 통해서 이해한바로는 다음과 같다. 

1부터 N까지의 정수를 오름차순으로 push하다가 일정 조건에서 pop한 숫자들을 순서대로 모았을 때 주어진 순열이 될 수 있는지

만들 수 있다면 그때까지의 push,pop 과정을 출력하고, 아니라면 NO를 출력한다. 

 

NO를 출력하는 상황은 stack의 끝 수가 주어진 숫자보다 큰 경우이다.  stack에 정수를 오름차순으로 push하기 때문에 해당 상황에는 주어진 순열을 만들 수 없기 때문이다.

예를 들자면, stack에 1 2 3 4 가 있고, 순열에 4, 1 ,,, 로 있다면 

stack[-1]과 순열[0]이 같으므로 stack의 4를 pop한다. 다음 3(stack[-1]) > 1(순열[0]) 이므로 1을 꺼내기 위해선 stack의 2, 3을 pop해야하므로 이렇게 되면 순열에서 2 또는 3을 만났을 때 stack에 pop할 수 있는 2, 3이 없게 된다. 따라서 주어진 순열을 만들 수 없게 된다. (오름차순으로 push하기 때문)

 

 

 

- 정답 풀이 : 참고한 블로그

• 주어진 숫자까지 stack에 푸시한다. cur은 어디까지 push했는지 확인하기 위한 변수이다. 
• stack[-1] == 주어진 숫자 라면 stack.pop()을 하고, '-'를 answer에 추가한다. 
• stack[-1] > num이라면 수열을 만들 수 없으므로 'NO'를 출력한 뒤 break 한다.

import sys
input = sys.stdin.readline

n = int(input())
stack, answer = [], []
flag, cur = 0, 1

for i in range(n):
    num = int(input())
    while cur <= num:
        stack.append(cur)
        answer.append('+')
        cur += 1
        
    if stack[-1] == num: #오름차순으로 숫자를 넣기 때문에 이렇게 할 수 있다
        stack.pop()
        answer.append('-')
    else:
        print('NO')
        flag = 1
        break
if flag == 0:
    for i in answer:
        print(i)