[백준/JAVA] 24511: queuestack

[백준/JAVA] 24511: queuestack

queuestack이라는 특정한 자료구조가 있고, 수열의 값을 입력받아 이를 자료구조에 넣는다. queuestack은 다음과 같이 동작한다.

1. 입력받은 수 x0을 1번 자료구조에 삽입한다.
2. 1번 자료구조에서 원소를 pop한다. 이 때 자료구조가 스택인지 큐인지에 따라 pop되는 원소가 다를 것이다.
3. pop된 원소를 x1이라고 하고 위의 과정을 2번 자료구조에 대해 실행한다.
4. xn이 구해질 때까지 반복하고 마지막에 xn을 리턴한다.

한 번 원소를 입력받을때마다 배열의 끝까지 순회를 해야 하는데, 이렇게 하면 딱봐도 시간이 엄청 많이 걸릴것 같다는 생각이 든다.

생각해보면 스택은 top에서만 원소를 넣고 뺄 수 있다. 스택 자료구조에 위 과정을 실행하게 되면 넣은 원소를 그대로 pop하게 되는 것이다. 따라서 배열의 변화는 큐에만 주목하면 된다.

예시 배열 $[1,2,3,4]$ 는 $[0,1,1,0]$이다. (큐, 스택, 스택, 큐)
입력으로 수열 $[2,4,7]$이 주어지고, $2$를 삽입할 때 진행과정은 다음과 같다.

$[2,2,3,4]$ : 1번 인덱스에 $2$를 삽입, $1$을 pop => 큐이므로
$[2,2,3,4]$ : 2번 인덱스에 $1$을 삽입, 다시 $1$을 pop => 스택이므로
$[2,2,3,4]$ : 3번 인덱스에 $1$을 삽입, 다시 $1$을 pop => 스택이므로
$[2,2,3,1]$ : 4번 인덱스에 $1$을 삽입, $4$를 pop => 큐이므로

따라서 마지막에 pop된 4를 리턴하게 된다. 이를 이후 $4, 7$에 대해서도 반복한다.

주목해볼 점은 스택에 대해선 신경쓰지 않으니 배열의 큐 자료구조 전체를 이어서 볼 수 있다는 것이다.

위에서 큐는 $[1,4]$이다. 스택인 $[2,3]$을 제외하고 여기에 입력으로 주어진 $2$를 rear에 push하면 $[2,1,4]$이다. 그리고 front에서 pop을 하면 스택은 $[2,1]$이고, pop된 원소는 4이다.

따라서 실행시간을 줄이기 위해서는 배열의 큐에만 주목하며 입력으로 받은 원소를 rear에 push, 그리고 큐의 front에서 pop하면 되는 문제이다.

소스코드

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw =
                new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        Deque<Integer> deque = new ArrayDeque<>();

        // arr[i][0] = 0이면 큐, 1이면 스택
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // 스택에 대해선 신경쓸 필요가 없으므로 큐 자료구조인 것만 저장
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (arr[i] == 0)
                deque.addLast(num);
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) {
            deque.addFirst(Integer.parseInt(st.nextToken()));
            bw.write(deque.pollLast()+" ");
        }
        bw.flush();
    }
}