[BOJ] 1874. 스택 수열

📌 문제 제목

문제 링크: BOJ 1874

---

🗒️ 문제 설명

임의의 수열이 주어졌을 때, 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop연산을 수행해야 하는지 알아내는 프로그램

스택에 push 하는 순서는 반드시 오름차순.

시간 제한: 2초

메모리 제한: 128MB

1 <= n <= 100,000

같은 정수가 두 번 나오는 일은 없다.

---

💡 문제 해결 아이디어

• push 하는 값을 저장하는 스택 필요
• 입력된 수열을 순회하며 수열에 push 해야할 값과 비교
  • push 해야할 값이 수열의 i번째 값보다 작거나 같을 때까지 값을 증가
  • push 해야할 값이 수열의 i번째 값보다 크다면 스택의 마지막 원소와 i번째 값 비교
    • 같으면 pop
    • 다르면 NO

---

⌛️ 시간 복잡도

• O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

n = int(input().strip())
seq = [int(input().strip()) for _ in range(n)]

result = []  # 스택
answer = []  # bool이 저장되는 배열 (True: push, False: pop)
x = 1

for s in seq:
    while x <= s:
        result.append(x)
        x += 1
        answer.append(True)

    if result[-1] == s:
        result.pop()
        answer.append(False)
    else:
        print("NO")
        exit(0)

for b in answer:
    print("+" if b else "-")