백준 1874번 [스택 수열](C++)-yes6686- 티스토리

백준 문제 풀이: 1874 [스택 수열]

---

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

문제 설명:

1부터 n까지의 수를 스택을 이용해 주어진 수열로 출력할 수 있는지 확인하고, 가능하다면 수행 과정을 출력합니다. 불가능하면 NO를 출력합니다.

---

문제 해결 코드

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

int arr[100001];
stack<int> s;
vector<char> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int k = 0;
    int j = 0;

    while (j < n) {
        if (k < arr[j]) {
            for (int i = k + 1; i <= arr[j]; i++) {
                s.push(i);
                v.push_back('+');
            }
            s.pop();
            v.push_back('-');
            k = arr[j];
            j++;
        } else {
            if (!s.empty() && s.top() == arr[j]) {
                v.push_back('-');
                s.pop();
                j++;
            } else {
                cout << "NO";
                return 0;
            }
        }
    }

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

---

코드 설명

• 핵심 아이디어: 스택을 활용하여 주어진 수열을 생성할 수 있는지 검증하고, 각 연산을 기록합니다.
• 구현 세부사항:
  • arr: 주어진 수열을 저장합니다.
  • s: 스택을 이용하여 수열을 생성합니다.
  • v: 연산 기록을 저장하는 벡터입니다.
  • 현재 스택에 들어가야 하는 최대값 k를 관리하며, 주어진 값 arr[j]에 도달할 때까지 푸시 연산을 수행합니다.
  • 스택의 맨 위 값이 원하는 값이라면 팝 연산을 수행하고, 그렇지 않으면 불가능을 의미하는 NO를 출력합니다.
• 시간 복잡도: O(n)
  • 푸시와 팝 연산은 각 숫자에 대해 한 번만 이루어지므로 효율적입니다.

---

결과

주어진 수열이 스택 연산으로 가능한 경우 연산 기록을 출력하며, 불가능하면 NO를 출력합니다. 추가적인 최적화가 필요하지 않은 간결한 풀이입니다.

다른 접근 방식이나 질문이 있다면 댓글로 남겨주세요!