백준 1874 스택 수열 / C++

문제 : 1874

풀이 point

스택을 통해 수열을 만들 수 있는지 파악한다.
1부터 수열의 맨 처음 숫자까지 stack에 넣는다. 벡터에 +를 넣어준다. 다음으론 stack의 top이 수열의 값과 같은지 확인한다. 벡터에 -를 넣어준다. 그렇지 않다면 수열로 만들 수 없다.

풀이 방법

stack.top은 스택이 비어있으면 런타임 에러가 발생하므로 미리 스택에 0을 푸쉬함으로써 방지한다.

코드

//백준 1874, 스택 수열

#include <iostream>
#include <stack>
#include <vector>

int sqc[100'000];
std::stack<int> stack;
std::vector<char> vec;

int main (){

    int N;
    std::cin >> N;
    for(int i{0}; i<N; ++i) std::cin >> sqc[i];
    
    stack.push(0);
    
    int curr{1}; bool flag = false;
    for(int i{0}; i<N; ++i){
        while(stack.top() < sqc[i]){
            stack.push(curr);
            vec.push_back('+');
            ++curr;
        }
        if(stack.top() == sqc[i]){
            stack.pop();
            vec.push_back('-');
        }
        else{
            flag = true;
        }

    }
    if(flag){
        std::cout << "NO";
        return 0;
    }
    for(auto c : vec) std::cout << c << '\n';

    return 0;
}

사족

이런 류의 문제는 솔직히 생각을 많이 해야하는 부분이 있다. 머리로는 가능한데 코드로 구현하는게 힘듬… 아무래도 생각을 프로그래밍 적으로 아직은 잘 못하나보다. 오히려 재귀 같은게 더 그런 사고를 지향하다보니 잘 되는듯… 이런 것도 많이 연습해야겠다.

2025-02-13T02:13:59.848Z