[백준] 1874번 : 스택 수열

---

🔗 문제 링크

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

---

반응형

728x90

👩‍💻 코드

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    cin >> N;
    
    vector<int> A(N, 0);
    vector<char> answer;
    stack<int> stk;
    int num = 1;
    
    for (int i=0; i<N; i++){
        cin >> A[i];
    }
    
    for (int i=0; i<N; i++){
        int a = A[i];
        
        if(a >= num){
            while (a >= num){
                stk.push(num++);
                answer.push_back('+');
            }
            
            stk.pop();
            answer.push_back('-');
        }else{
            int t = stk.top();
            stk.pop();
            
            if(t > a){
                cout << "NO";
                return 0;
            }else{
                answer.push_back('-');
            }
        }
    }
    
    for(int i=0; i<answer.size(); i++){
        cout << answer[i] << "\n";
    }
    
    return 0;
}

---

📝 풀이

Do it! 알고리즘 코딩테스 - C++ 편 : 기출 유형 분석부터 문제 풀이 비법까지!를 참고하였습니다.

 

현재 수열의 수가 스택에 저장할 수보다 크다면 스택에 현재 수열의 수까지 push 합니다.push가 끝나면 수열을 출력하기 위해 pop을 한 번 합니다.

 

현재 수열의 수가 스택에 저장할 수보다 작으면 스택에서 pop 합니다.만약 스택위 top이 수열의 수보다 크다면 수열을 출력할 수 없으므로 "NO"를 출력하고 return 합니다.

 

최종적으로 수열을 만들기 위한 연산이 들어 있는 answer을 출력해줍니다.