[필수 문제] 접시

1. 문제

접시 a, b, c, d 가 있고, 알파벳 순으로 한쪽이 막혀 있는 세척기에 들어간다고 할 때, b a c d 순으로 꺼내기 위해서는 push, push, pop, pop, push, pop, push, pop을 하면 된다. 세척기에서 꺼내는 순서가 주어질 때 그 동작을 출력하는 프로그램을 작성하시오. 만약 주어진 순서대로 접시를 꺼낼 수 없다면 “impossible”을 출력한다.

---

입력

첫째 줄에 소문자 알파벳이 주어진다. 중복된 소문자 알파벳은 입력되지 않는다. 알파벳 소문자는 26개이다. 입력되는 알파벳의 길이는 최대 26 자리이다.  

출력

접시를 꺼내는 것이 가능한 경우 push, pop의 순서를 출력한다. 이것이 불가능하다면 impossible을 출력한다.  

예제 입력

case 1) bacd

case 2) dabc

예제 출력

case 1)

push
push
pop
pop
push
pop
push
pop

 

case 2)

impossible

 

 

 

2. 풀이

이 문제의 풀이는 간단하다. 스택에 알파벳 'a'부터 하나씩 넣어보면서 주어진 문자열의 각 요소를 비교하여 동일할 경우 pop, 동일하지 않을 경우 알파벳을 하나씩 증가시키면서 push하면 된다.

import java.io.*;
import java.util.Stack;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        Stack<Character> stack = new Stack<>();

        String str = br.readLine();
        int strIdx = 0;

        char item = 'a';
        int itemIdx = 0;

        int[] result = new int[60]; // 알파벳 26 * 2
        int resultIdx = 0;

        boolean flag = false;
        while(true) {
            char topElement = stack.isEmpty() ? 0 : stack.peek();

            if(topElement != str.charAt(strIdx)) {
                if(itemIdx >= str.length()) { // 넣을 수 있는 알파벳의 범위를 넘었을 경우
                    flag = false;
                    break;
                }

                stack.push((char)(itemIdx + (int)item));
                itemIdx++;

                result[resultIdx++] = 0; // push

            } else {
                stack.pop();
                strIdx++;

                result[resultIdx++] = 1; // pop

                if(strIdx >= str.length()) { // 주어진 문자열을 모두 확인했을 경우
                    flag = true;
                    break;
                }

            }
        }
        
        if(flag) {
            for(int i = 0; i < resultIdx; i++) {
                if(result[i] == 0) bw.write("push\n");
                else bw.write("pop\n");
            }
        } else bw.write("impossible");


        br.close();
        bw.flush();
        bw.close();
    }

}