[C++]Stack 자료구조 - 기차운행

올바른 괄호 문제는 배열에 있는 값과 Stack의 Top자료를 비교했다면
이 문제는 출력값과 Stack의 Top자료를 비교한다.
출력값에 규칙성이 있다면(정렬된 값) 이를 이용하여 출력값과 Top자료가 동일할 때 POP하는 방식으로 구현한다.

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

using namespace std;

int main() {
    int N,i,j=1;
    scanf("%d",&N);
    int a;
    stack<int> st;
    vector<char> str(N);
    
    for(i = 1; i <= N; i++){
        scanf("%d",&a);
        st.push(a);
        str.push_back('P');
        
        while(1){
            if(st.empty()) break;
            if(st.top() == j){ //이게 굉장히 유용
                st.pop();
                str.push_back('O');
                j++;
            }else break;
        }
    }
    
    if(!st.empty()) printf("impossible\n");
    else {
        for(i = 1; i <= str.size(); i++){
            printf("%c",str[i]);
        }
    }
    
    return 0;
}

• 이 문제는 딱 보면 Stack문제라는 것을 알 수 있다(push, pop이라는 힌트까지 줬음)
• 단 여기서 얻어갈 수 있는 것은 값의 출력을 결국 정렬된 값으로 출력하게 되는데
• while문에서 j변수를 이용하여 뽑아낼 값이 정렬될 값과 동일한지를 체크하고 동일하다면 Out하는 것이다.
• 출력문이 정렬되는 값으로 정해져있기 때문에 처음에 출력되어야하는 값은 무조건 1이다.

1. top이 가리키는 값이 1(j)인지 비교해서 1이라면 Out시키고 j++을 한다.
2. 그 다음 값 top이 가리키는 값이 2(j)인지 비교해서 2라면 Out시키고 j++한다.
3. 만약 top이 가리키는 값과 j값이 동일하지 않다면 그냥 push만 하는 것이다.

• 처음에는 올바른 괄호 문제처럼 배열에 있는 값과 stack의 top과 비교하여 stack의 값이 더 작으면 pop하고 stack의 값이 더 크면 push하는 식으로 했다. 하지만, 출력값이 정렬된 값이고 입력값이 1~N의 수라면은 j변수를 이용하는 것이 매우 유용하다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard