백준 1874 - 스택수열 (C++풀이)

📌 백준 1874번: 스택 수열 (C++ 풀이)

🔗 문제 링크 (백준 1874번)

---

✅ 문제 요약

스택은 LIFO(Last In First Out) 구조로, 나중에 들어간 게 먼저 나오는 구조다.
이 문제는 1부터 N까지의 수를 오름차순으로 push하면서,
임의의 수열이 만들어질 수 있는지를 판단하고,
가능하면 push(+), pop(-) 연산 순서를 출력해야 한다.

예시:

입력
8
4
3
6
8
7
5
2
1

출력
+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

---

📌 문제 조건 핵심

• 숫자는 무조건 1부터 N까지 오름차순으로만 push 가능
• 필요한 숫자가 나올 때까지 계속 push
• 나오면 pop, 아니라면 “NO” 출력하고 끝내야 함

---

🧠 내가 처음에 틀렸던 이유

처음에는 걍 스택 상태를 하나하나 계산하면서,
“지금 스택에서 이 숫자 pop할 수 있냐?” 를 무식하게 따지려고 했음.

근데 이 방식은 오름차순 push 조건을 제대로 안 활용해서
로직이 지저분해지고 예외 케이스 막히더라.

---

💡 핵심 아이디어

“다음으로 push할 숫자(next)를 추적하면서,
그 수보다 작거나 같을 때까지 push하고
스택 top이 원하는 숫자랑 맞으면 pop”
이 흐름만 정확히 구현하면 됨.

---

✅ 정답 코드 (C++)

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main()
{
    int n, next = 1;
    cin >> n;

    stack<int> s;
    vector<char> calc;

    for (int i = 0; i < n; i++) {
        int find;
        cin >> find;

        // push 해야 할 숫자 도달할 때까지 push
        while (next <= find) {
            s.push(next++);
            calc.push_back('+');
        }

        // 스택 top이 원하는 숫자면 pop
        if (s.top() == find) {
            s.pop();
            calc.push_back('-');
        }
        else {
            cout << "NO";
            return 0;
        }
    }

    for (char c : calc) {
        cout << c << '\n';
    }

    return 0;
}

---

🗒 회고

처음에 그냥 아무 생각 없이 구현하다가 “스택을 연산처럼 직접 시뮬레이션” 하려다 개삽질함.
결국 조건을 잘 읽고, 순차적으로 push해야 한다는 점에서
next라는 추적 변수를 도입하는 게 핵심이었음.

---

✍ 마무리

이 문제 덕분에 “무지성 구현” 습관에서 조금은 벗어날 수 있었던 듯.
앞으로도 그냥 구현부터 달리지 말고,
조건에서 뭘 활용할 수 있을지를 먼저 파악하자.

---

#스택 #자료구조 #중급 #복습필요 #C++