접시

문제

접시 a, b, c, d 가 있고, 알파벳 순으로 한쪽이 막혀 있는 세척기에 들어간다고 할 때, b a c d 순으로 꺼내기 위해서는
push, push, pop, pop, push, pop, push, pop을 하면 된다.

 

세척기에서 꺼내는 순서가 주어질 때 그 동작을 출력하는 프로그램을 작성하시오.

 

만약 주어진 순서대로 접시를 꺼낼 수 없다면 “impossible”을 출력한다.

 

 

입력

첫째 줄에 소문자 알파벳이 주어진다.

중복된 소문자 알파벳은 입력되지 않는다.

알파벳 소문자는 26개이다.

입력되는 알파벳의 길이는 최대 26 자리이다. 

 

 

출력

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

이것이 불가능하다면 impossible을 출력한다.

 

 

입력 예시 1

bacd

 

 

출력 예시 1

push
push
pop
pop
push
pop
push
pop

 

 

입력 예시 2

bacd

 

 

출력 예시 2

push
push
pop
pop
push
pop
push
pop

 

 

코드

Java

import java.util.*;

public class Main {
    static class Stack {
        int[] arr = new int[26];
        int cursor = 0;

        int push(int number) {
            if (26 <= cursor) {
                return -1;
            } else {
                arr[cursor++] = number;
                return cursor;
            }
        }

        int pop() {
            if (cursor == 0) {
                return -1;
            } else {
                cursor--;
                return cursor;
            }
        }

        int top() {
            if (cursor == 0) {
                return -1;
            } else {
                return arr[cursor - 1];
            }
        }

        int size() {
            return cursor;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Stack stack = new Stack();

        String str = scan.nextLine();
        char[] chars = str.toCharArray();
        int current = 'a';
        int endChar = current + chars.length;
        int cursor = 0;

        String[] results = new String[100];
        int resultSize = 0;

        while (current < endChar) {
            if (stack.size() == 0) {
                stack.push(current++);
                results[resultSize++] = "push";
                continue;
            }

            if (stack.top() == chars[cursor]) {
                stack.pop();
                cursor++;
                results[resultSize++] = "pop";
            } else {
                stack.push(current++);
                results[resultSize++] = "push";
            }
        }
        while ((cursor < chars.length) && (stack.top() == chars[cursor])) {
            stack.pop();
            cursor++;
            results[resultSize++] = "pop";
        }

        if (stack.size() == 0) {
            for (String result : results) {
                if (result == null) break;
                System.out.println(result);
            }
        } else {
            System.out.println("impossible");
        }
    }
}