문제 출처

단계별로 풀어보기 > 스택 큐 덱 > queuestack
https://www.acmicpc.net/problem/24511

문제 설명

N개의 자료구조(1~N)로 구성 된 queuestack이 있을 때, 각각의 자료구조에는 한 개의 원소가 들어있다.
자료구조는 queue or stack으로 구성되어있으며,
M개의 원소가 주어질 때, 각 원소는 N개의 자료구조를 지나면서 push 된 후, 다시 pop한 결과가 다음 자료구조로 들어가는 형태이다.
마지막에 나온 자료구조들의 결과를 출력하라.

접근 방법

Stack의 경우 push, pop 의 순서로 진행하면, 들어갔던 것이 바로 나오는 형태이고,
Queue의 경우 push, pop 의 순서로 진행하면, 원래 자료구조 안에 있던 원소가 다음으로 가는 원소가 되고, 새로운 원소가 그 자리를 차지하는 형태이다.

deque을 이용하여 자료구조가 queue인 경우만 각각 offerLast를 진행한다.
그리고, M개의 원소가 들어갈 때, 새로운 원소는 offerFirst, 결과값으론 pollLast의 원소를 저장하여, M번 진행되면 그 결과를 출력한다.

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

public class queuestack {

    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[] type = new int[N];
        int[] num = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        Deque<Integer> queue = new ArrayDeque<>();

        for(int i = 0; i<N; i++){
            type[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());

        for(int i = 0 ; i<N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
            if (type[i] == 0){
                queue.offerLast(num[i]);
            }
        }

        int M = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i<M; i++){
            int next = Integer.parseInt(st.nextToken());
            queue.addFirst(next);
            next = queue.removeLast();
            sb.append(next).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }

}

Review

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class queuestack_review {

    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[] type = new int[N];
        int[] value = new int[N];

        Deque<Integer> dq = new ArrayDeque<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i<N; i++){
            type[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());

        for(int i = 0; i<N; i++){
            value[i] = Integer.parseInt(st.nextToken());
            if (type[i] == 0) {
                dq.addLast(value[i]);
            }
        }

        int M = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i<M; i++){
            dq.addFirst(Integer.parseInt(st.nextToken()));
            int k = dq.pollLast();
            sb.append(k).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

}

알게된 점

처음에 이 문제를 접했을 땐, 정말 stack, Queue를 List안에 삽입, 즉, 자료구조들을 삽입하여 실제로 push, pop하는 과정을 진행했지만, 이는 시간초과(1초)되어서 틀렸다.
아마 이중 for문 때문인 것 같다.

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

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));

        List<Object> list = new ArrayList<>();

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i<N; i++){
            int kind = Integer.parseInt(st.nextToken());
            if(kind == 0 ){
                Queue<Integer> qs = new LinkedList<>();
                list.add(qs);
            } else {
                Stack<Integer> qs = new Stack<>();
                list.add(qs);
            }
        }

        st = new StringTokenizer(br.readLine());


        for(int i = 0; i<N; i++){
            int k = Integer.parseInt(st.nextToken());
            Object place =list.get(i);
            if(place instanceof Queue<?>){
                ((Queue<Integer>) place).offer(k);
            } else {
                ((Stack<Integer>) place).push(k);
            }
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int next = 0;
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i<M; i++){
            int k = Integer.parseInt(st.nextToken());
            Object first = list.get(0);
            if(first instanceof Queue<?>){
                ((Queue<Integer>) first).offer(k);
                next = ((Queue<Integer>) first).poll();
            } else {
                ((Stack<Integer>) first).push(k);
                next = ((Stack<Integer>) first).pop();
            }

            for(int j = 1; j<N; j++){
                Object place = list.get(j);
                if(place instanceof Queue<?>){
                    ((Queue<Integer>) place).offer(next);
                    next = ((Queue<Integer>) place).poll();
                } else {
                    ((Stack<Integer>) place).push(next);
                    next = ((Stack<Integer>) place).pop();
                }
            }
            sb.append(next).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }

}

Review
먼저 들어가는 요소는 addLast로 들어가서 deque의 앞쪽에 있게 한다.
이 후 새로운 원소들을 삽입할 때, addFirst하고, 가장 마지막 요소를 자료구조에서 빼내기 위해 pollLast하여 StringBuilder에 저장한다.

문제푼 흔적

Review