군대에서_코딩하기_알고리즘_22

오늘은 stack을 응용한 문젠데, A도시에서 출발한 기차는 B도시로 도착한다고 가정할 때, 도로 중간에 있는 T자형 교차로에서 기차 도착 순서를 조정한다.

P작업은 A도시에서 오는 기차를 교차로에 넣는것을 의미하고,O작업은 교차로에 들어온 가장 최근 기차를 B도시로 보내는 것을 의미한다.
예를 들어 2 1 3 기차 번호 순으로 A도시에서 출발하더라도 교차로를 이용해 B도시에는 1 2 3 순으로 도착하게 하는 것이다.
이 때 작업은 P P O O P O 순으로 하면 B도시 1 2 3 순으로 도착한다.

N(기차 개수) 과 기차번호를 입력하여 작업 순서를 출력해야 한다.

우선 별로 어렵지 않은 문제라고 생각해서, 바로 stack을 사용해 접근을 했고 그 결과는 상당히 처참했다. 이유는 모르겠는데 컴파일이 돌아가는 과정에서 계속 프로그램이 강제 종료..?된다고 해야하나.. stack.pop()을 이용해서 stack을 비워주는 과정에서 인덱스 오류가 나는건지 도무지 이유를 찾을 수가 없었다.. 그래서 한 하루 이틀정도 고민하다가 그냥 인강을 봤고 코드를 조금 참고했다.
근데 확실히 코드가 좀 안정적..?이라고 해야하나, vector 배열을 따로 만들어서 순서를 비교해주는 것도 그렇고, 작업을 push_back으로 일일이 저장했다가 나중에 한꺼번에 출력하는 것도 뭔가 나와는 달랐다.
나는 그냥 바로바로 출력하고, 그냥 변수 하나 만들어서 ++ 해주면서 비교했는데..
아무튼 코드는 다음과 같다.

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

using namespace std;

int main(){
    
    int N, i, check=1;
    cin>>N;
    
    vector<int> train(N+1);
    vector<int> temp(N+1);
    
    for(i=1; i<=N; i++){
        cin>>train[i];
        temp[i] = i;
    }
    
    vector<char> work;
    stack<int> cross;
    
    for(i=1; i<=N; i++){
        cross.push(train[i]);
        work.push_back('P');
        while(true){
            if(cross.empty()){
                break;
            }
            if(cross.top()==temp[check]){
                work.push_back('O');
                check++;
                cross.pop();
            }
            else{
                break;
            }
        }
            
    }
    
    if(cross.empty()){
        for(i=0; i<work.size(); i++){
        cout<<work[i];
        }
    }
    else{
        cout<<"impossible";
    }
    
    
}