[인프런 알고리즘 문제풀이] 기차 운행

문제

인프런 알고리즘 문제풀이

• The copyright in this matter is in Inflearn

입력1

3
2 1 3

출력1

PPOOPO

풀이

a도시에서 출발한 기차는 b도시로 도착해야하는데, 중간에 교차로가 있어 도착 순서를 조정할 수 있다.
예를 들어, a도시에 입력된 값이 2 1 3 일때
입력된 결과가 오름차순 1,2,3으로 b도시에 도착하려고 한다면
교차로에서 push와 pop의 과정을 어떤 순서로 해야 1,2,3이 나오는지 결과를 출력하는 문제이다.

1. j = 0이라는 변수가 있고, s 배열 = {2,1,3}의 맨 처음 값 2를 스택에 push하고
   "P"를 string형 str 변수에 붙인다.
2. 스택에 맨 윗값인 2와 j+1= 1을 비교하여 같지 않으니 넘어간다.
3. s배열의 그 다음 값 1을 push하고, "P"를 str에 붙인다.
4. 스택 맨 윗값 1과 j+1 = 1이 같으니 pop하고 str에 "O"를 붙인다.
   그리고 j는 1증가하여 j = 1이 된다.
5. 그 다음 스택 맨 윗값 2와 j+1 = 2가 같으니 pop하고 str에 "O"를 붙인다. j도 1증가하여
   j = 2가 된다.
6. 스택이 비었으니 스택에 s 배열 그 다음값 3을 push하고 "P"를 str에 붙인 후,
   j+1 = 3과 값이 같으니 다시 pop하고 "O"붙인 후 종료.

코드

/*55. 기차 운행(스택 자료구조 응용)*/
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.StringTokenizer;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        
        System.setIn(new FileInputStream("input.txt"));
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int[] s = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0;i<n;i++){
            s[i] = Integer.parseInt(st.nextToken());
        }

        Stack<Integer> stack = new Stack<>();
        String str = "";
        int j = 0;
        for(int i = 0;i<n;i++){
            stack.push(s[i]);
            str += "P";
            while(!stack.empty()){
                if(j+1 == stack.peek()){
                    j++;
                    stack.pop();
                    str += "O";
                }else{
                    break;
                }
            }
            
        }

        if(!stack.empty()) {System.out.println("impossible");
        }else{
            System.out.println(str);
        }


    }
}