[Baekjoon, C++] 1874번 : 스택 수열

백준 단계별 풀기에서 스택 5번째 문제이다.

링크는 아래와 같다.

www.acmicpc.net/problem/1874

1874번: 스택 수열

---

백준 1874번 문제, 입력, 출력

---

백준 1874번 입,출력 예제 1,2

---

문제를 보고 바로 이해하기 어려웠다. 입출력 예제를 보면서 결과를 따라가본 후에야 어떤 문제인지 알게 되었다. 기존에 풀었던 스택 문제와는 난이도가 있었다. 이전 문제들은 문제를 보고 바로 어떤식으로 풀어야 겠다라는 그림이 바로 그려졌었는데, 이번은 아니였다.

---

1. int 타입 변수를 하나 선언하고, 입력 받을 수열의 길이를 정한다.  

---

2. 수열을 입력받는다. 여기서 어떤 방식으로 입력을 받을지에 대한 고민이 있었다. int[] 배열, queue 라이브러리 또는 vector 라이브러리를 쓸 수 있을 것 같다. 이번 문제에서는 queue 라이브러리를 사용할 것이다. 한 줄에 하나씩 정수 값을 받기 때문에, for문으로 정수 값을 받을때마다, queue에 넣어준다. queue.push(정수값)

---

3. 어떤 방법으로 입력받은 수열을 처리해야 할까? 1 2 3 4 5 6 7 8 이라는 수열을 4 3 6 8 7 5 2 1로 만들기 위해서 필요한게 무엇일까? 제일 처음으로 입력 받은 수열의 정수 값까지는 스택에 무조건 넣어줘야한다. 열을 세우기 위해서는 스택에서 pop을 함으로써, 세워질 수 있기 때문이다.

 그리고 스택에서 push는 1 2 3 4 5 6 7 8 순서대로 들어가게 된다. 1 2가 들어가고 다음에 3 4 5 ···가 들어가든 1 2 3 이 들어가고 4 5 ···가 들어가든 한번에 들어가는 양은 다르지만, 결과적으로 스택에 push는 1 2 3 4 5 6 7 8 로 들어간다. 그래서 스택에 현재 어디까지 push가 되었는지를 가리키는 변수(a)를 하나 둬서 push를 수행할 때 마다 1씩 증가시킨다.

---

 4. 반복문을 사용한다. 탈출 조건은 큐에 더이상 남은 정수가 없을때이거나, NO라는 것이 결정될 때이다. 반복내용은 큐의 제일 앞의 숫자를 받는다. 스택의 top과 비교한다. 큐의 제일 앞의 숫자가 top보다 크거나 혹여 스택이 비었다면, 스택에 (++a)를 push(+)한다. 아니면 만약 큐의 제일 앞의 숫자가 스택의 top과 일치한다. 그러면 스택에서 해당 숫자를 pop(-), 큐에서도 제일 앞의 숫자를 pop한다. 아니면 만약에 큐의 제일 앞의 숫자가 스택의 top보다 작다면, NO가 된다.  

---

5. string 변수(b)를 하나 둬서, 스택에 push와 pop 할때마다, 해당 변수에 + -를 추가한다. 그리고 반복문이 끝난 뒤에 NO가 아니라면, 해당 변수(b)를 출력한다. 

boolean 타입의 변수를 둬서, 반복문에서 NO일 때 false를 저장한다. 그리고 string 변수(b) 출력 전 if문으로 조건을 확인한다.    

---

 

#include<iostream>
#include<stack>    // 표준 라이브러리 stack을 사용하기 위함
#include<queue>

using namespace std;

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

    int sizeOfsequence;
    int num;
    stack<int> st;
    queue<int> que;
    string seq_completed;
    int stStartNum;
    bool isNo = false;

    cin >> sizeOfsequence;

    for (int i = 0; i < sizeOfsequence; i++) {    
        cin >> num;
        que.push(num);
    }

    for (int i = 1; i <= que.front(); i++) {
        st.push(i);
        seq_completed += '+';
    }
    stStartNum = que.front();
    st.pop();
    que.pop();
    seq_completed += '-';

    while (1) {
        if (que.empty()) {
            break;
        }

        int nowNumFromQueue = que.front();
        
        if (st.empty() || st.top() < nowNumFromQueue) {
            st.push(++stStartNum);
            seq_completed += '+';
        }
        else if (st.top() == nowNumFromQueue) {
            st.pop();
            que.pop();
            seq_completed += '-';
        }
        else if (st.top() > nowNumFromQueue) {
            isNo = true;
            break;
        }

    }

    if (isNo) {
        cout << "NO\n";
    }
    else {
        for (int i = 0; i < seq_completed.size(); i++) {
            cout << seq_completed[i] << "\n";
        }
    }
    return 0;
}