55. 기차운행[stack 활용]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

3

2 1 3 

 

출력예제 1

PPOOPO

 

풀이 

- A도시에서 B도시로 갈 때 교차로를 거쳐서 나온다

- 순서가 역전되있더라도 교차로에서 나올때는 1,2,3순서 맞게 나와야한다

- 순서를 비교할 변수 j=1로 초기화한다. 1을 증가시키면서 1, 2, 3 순서에 맞게 비교한다.

- 일단 스택에 수를 넣으면 'P'를 문자열 벡터에 넣는다.

- 스택에 넣은 값(현재 top)값과 j(현재 1번)가 같으면, pop하면서 'O'를 문자열 벡터에 넣는다.

- pop하고 1번순서는 해결되었으므로 j++시켜 2번으로 만들고, 현재(top)과 비교 해서 같으면 연속해서 뺀다.

- 이 부분에서 while문을 써서 연속해서 순서 맞으면 계속 빼다 top과 j가 같지 않으면 break하고 다시 입력받는다.

- 마지막까지 스택에 자료가 남아있으면 impossible(순서대로 뺄 수 없음) 을 의미한다.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
int arr[31];

//55. 기차운행(stack)



int main(){

    int n, i, j=1, m;

    stack<int> s;

    scanf("%d", &n);

    vector<char> str; //push_back으로 넣으면 공간 생김

    for(i=1;i<=n;i++){

        scanf("%d", &m); //기차 읽기

        s.push(m);

        str.push_back('P');

        while(1){

            if(s.empty()) break; //값 없으면 break

            if(j==s.top()){

                //s.top()이랑 j랑 맞으면 계속 꺼냄

                s.pop();

                j++;

                str.push_back('O');

            }

            else break; //같지 않으면 넘어감

        }

    }

    

    if(!s.empty()) printf("impossible");

    else {

        for(i=0;i<str.size();i++){

            printf("%c", str[i]);

        }

    }

    return 0;

}