[백준] 1874번 : 스택 수열

문제

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

풀이

[백준] 1874번 : 스택 수열 🥈(실버 2)
🎯 37.623%
⏰ 걸린 시간 : 30분

• 알고리즘 유형 : [스택]

📌 [포인트]

0. 수열의 현재위치의 값 보다 작은 수들을 STACK에 밀어 넣을 것인가?
1. 그렇지 않은 값들은 하나씩 빼서 넣어준다. 그때마다 수열의 값과 비교해서 가능한지 안한지를 판단

✔️ [문제풀이]
0. 수열의 현재 위치의 값들보다 작은 수는 STACK에 넣어준다.
1. 넣어주는 것은 +를 빼주는 것은 -를 answer에 넣어서 관리한다.
2. 수열을 만들 수 있는지 없는지 Flag를 사용해서 관리한다.

• 2-1. flag를 사용하는 이유는 ?
• 2-2. 중간에 NO를 출력했을때에도 answer의 전체를 출력하면 안되기 때문이다.

코드(code)

import sys
from collections import deque
N = int(input())
sequence = []
stack = deque()
answer = []
flag = 0

for i in range(N):
    a = int(input())
    sequence.append(a)

cur = 1  # 1부터 N까지의 수를 넣어주기 위한 수
for i in range(N):
    while cur <= sequence[i]:
        stack.append(cur)
        cur += 1
        answer.append('+')
    if stack[-1] == sequence[i]:
        stack.pop()
        answer.append('-')
    else:
        print("NO")
        flag = 1
        break
if flag == 0:
    for operator in answer:
        print(operator)

회고

스택의 문제는 익숙하지만, 이 문제에서 포인트라고 생각되는 것에 접근하는 법이 부족해서 시간이 오래걸렸다.

• [해당 코드]

  https://github.com/JamesJoe0830/ps_study/blob/main/Stack/1874(%EC%8A%A4%ED%83%9D%20%EC%88%98%EC%97%B4).py