문제
접시가 a, b, c, d 가 있고, 알파벳 순으로 한쪽이 막혀 있는 세척기에 들어간다고 할 때, b a c d 순으로 꺼내기 위해서는 push, push, pop, pop, push, pop, push, pop을 하면 된다. 세척기에서 꺼내는 순서가 주어질 때 그 동작을 출력하는 프로그램을 작성하시오. 만약 주어진 순서대로 접시를 꺼낼 수 없다면 “impossible”을 출력한다.
입력
첫째 줄에 소문자 알파벳이 주어진다. 중복된 소문자 알파벳은 입력되지 않는다. 알파벳 소문자는 26개이다.
출력
접시를 꺼내는 것이 가능한 경우 push, pop의 순서를 출력한다. 이것이 불가능하다면 impossible을 출력한다.
예제 입력
bacd
예제 출력
push
push
pop
pop
push
pop
push
pop
예제 입력
dabc
예제 출력
impossible
나는 먼저 alpha[] 배열에 a~z까지 저장하고, arr[] 배열에 주어진 예제를 저장하였다. 그리고 impossible 인지 아닌지 마지막에 판단해서 출력해야 되기 때문에, String 타입의 ans[] 배열에 차례대로 push 나 pop을 넣어 마지막에 pop의 개수가 예제의 개수와 같은지 판단하여 impossible 인지 아닌지 출력하게 코드를 구성했다. alpha 배열은 idx, arr배열은 top, ans 배열은 temp를 이용하여 인덱스를 컨트롤 하였다.
< 문제 풀이 >
1. alpha 배열과 arr 배열의 처음부터 비교하여 같으면 idx와 top을 증가시키고 push와 pop을 ans배열에 차례 대로 넣는다.
2. 이부분에서 내가 많이 고민해서 문제풀기가 어려웠는데, 예를 들어 예제로 cbad 가 주어진다면, 문제의 답은 push push push pop pop pop push pop 으로 답이 정해져있다. alpha 배열과 arr배열이 'c'일때 같아 지므로 그때 push pop을 하고, 그전까지는 push를 하는데, 문제는 방금 비교한 'c' 전에 'b' 'a'가 push 되어있다는 점이다. 다음에 나올 arr 배열에 바로 'b' 'a'가 있기 때문에, 그 전에 'b' 와 'a'가 있는지 탐색해야하는데, 이부분이 while문안에 있는 while문이다. 지금까지 비교한 idx값은 변화하면 안되기 때문에, idx-2 값을 x에 저장한 후에 이제부터 나올 arr값과 같은 값이 지금까지 비교했던 alpha 배열 전에 안나올때까지 탐색해서, 나오면 pop 해야한다.
3. alpha 배열과 arr 배열이 같지 않으면 ans 배열에 push 를 넣고, idx 만 증가시켜 alpha 배열의 알파벳을 하나 증가시킨다.
4. 다 비교하여 나오게 되면, pop의 개수를 cnt에 저장하여 예제로 들어온 알파벳 개수와 같은지 비교하여 정답을 출력한다.
