[C++/스택] 백준 1874 스택수열

1. 문제

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

1874번: 스택 수열

 

2. 풀이

큐에 출력 해야 하는 순서를 넣고, 스택에 수들을 넣었다 빼며, 답을 넣는다.
숫자들은 오름차순으로 스택에 들어가므로 현재 스택에 들어갈 숫자를 변수로 잡아 이를 증가시키며 스택에 숫자를 넣는다.

while문을 통해 큐의 원소가 없을 때 까지, 즉 모든 숫자를 출력할 때 까지 아래의 과정을 반복한다.
while문 내에는 3가지 조건이 있다.
* 현재 출력할 순서의 숫자가 스택에 없는 경우
- while문을 반복해 출력할 숫자가 들어갈 때까지 스택에 숫자를 오름차순으로 넣는다
- 스택에 숫자를 넣는 과정은 '+'이므로 정답을 넣는 스택에 '+'를 넣는다
* 스택의 맨 위에 출력할 숫자가 있는 경우
- 스택의 맨 위에 출력할 숫자가 있는 경우, 출력에 성공한 것이므로 스택의 가장 위 원소와 큐의 가장 아래 원소를 제거한다.
- 스택에 숫자를 빼는 과정은 '-'이므로 정답을 넣는 스택에 '-'를 넣는다.
* 위의 두가지 경우가 모두 아닌 경우
- 불가능한 경우이므로 "NO"를 출력하고 프로그램을 종료한다.

 

3. 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main() {
    int n, num;
    queue<int> inputOrder; // 출력해야 할 순서가 담긴 큐
    vector<int> s; // 수들을 순서대로 넣을 스택
    vector<char> ans; // 답
    scanf("%d", &n);
 
    // 출력할 순서를 입력
    for(int i = 0; i < n ;i++){
        scanf("%d", &num);
        inputOrder.push(num);
    }
 
    int now = 1; // 현재 넣을 숫자
    while(!inputOrder.empty()){
        if(now <= inputOrder.front()){ // 현재 출력해야 할 숫자가 스택에 없는 경우
            while(now <= inputOrder.front()){ // 스택에 출력할 숫자가 들어갈 때까지
                s.push_back(now++); // 스택에 숫자 오름 차순으로 넣음
                ans.push_back('+'); 
            }
        }else if(!s.empty() && s.back() == inputOrder.front()){ // 현재 출력해야 할 숫자가 스택의 끝에 있는 경우
            s.pop_back(); // 스택에서 숫자를 pop
            inputOrder.pop();
            ans.push_back('-');
        }else{ // 불가능한 경우
            printf("NO\n");
            return 0;
        }
    }
 
    // 답 출력
    for(int i = 0; i < ans.size(); i++){
        printf("%c\n", ans[i]);
    }
 
}