[백준] 24511번(Java)

📖 queuestack

[ 문제 ]
한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 queuestack이다.

queuestack의 구조는 다음과 같다.
$1$번, $2$번, ... , $N$번의 자료구조(queue 혹은 stack)가 나열되어있으며, 각각의 자료구조에는 한 개의 원소가 들어있다.
queuestack의 작동은 다음과 같다.
 

• $x_0$을 입력받는다.
• $x_0$을 $1$번 자료구조에 삽입한 뒤 $1$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 $x_1$이라 한다.
• $x_1$을 $2$번 자료구조에 삽입한 뒤 $2$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 $x_2$이라 한다.
  ...
• $x_{N-1}$을 $N$번 자료구조에 삽입한 뒤 $N$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 $x_N$이라 한다.
• $x_N$을 리턴한다.
  도현이는 길이 $M$의 수열 $C$를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 $1$ 참고)
  

queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.

💡풀이

• 해당 문제를 일반 배열을 이용해 풀이하려고 했으나 시간초과가 계속 나서 큐로 바꿔서 문제를 풀었다.
• 각 자료구조에는 하나의 원소만 들어갈 수 있다는 점을 이용했다.
• 자료구조가 스택인 경우 제일 나중에 들어간 값이 바로 나오기 때문에 스택은 따로 Stack 클래스나 Deque 클래스를 구현해주지 않고 그냥 스킵해도 무방하다.
• 큐의 경우에는 새로 들어온 값과 이전 값을 바꿔치기하는 셈.
• 필자는 모든 큐들을 하나의 큐로 보고, 값이 새롭게 들어올 때 새 값을 제일 앞에 넣고 다 한 칸씩 밀며 제일 끝에 있는 값이 출력되도록 구현했다.
• ex) [1, 3, 4, 6] 이라는 큐에 2라는 값을 추가한다고 했을 때의 결과는 [2, 1, 3, 4]가 되고, 출력되는 값은 6이 되는 셈.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Queue;
import java.util.StringTokenizer;

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


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N개의 자료구조
        int N = Integer.parseInt(br.readLine());
        Deque<Integer> stack = new ArrayDeque<>();
        Deque<Integer> queue = new ArrayDeque<>();
        StringBuilder ans = new StringBuilder();

        // 자료구조 유형 -> 1이면 스택, 0이면 큐
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        // 자료구조 내에 담긴 값들
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        for(int i = 0 ; i < N ; i++) {
            int typ = Integer.parseInt(st1.nextToken());
            int val = Integer.parseInt(st2.nextToken());
            if(typ == 0) {
                queue.add(val);
            }
        }

        int M = Integer.parseInt(br.readLine());
        StringTokenizer st3 = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < M ; i++) {
            int t = Integer.parseInt(st3.nextToken());
            queue.push(t);
            t = queue.pollLast();
            ans.append(t).append(" ");
        }

        System.out.println(ans);


    }
}

백준 24511번 : https://www.acmicpc.net/problem/24511