[백준 문제 풀이] 24511번 queuestack

Junu Kim·2026년 1월 13일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

84/89

[24511] queuestack

난이도: ★★☆☆☆ • solved on: 2026-01-13

문제 요약

문제 유형: 자료구조(Queue/Stack), 시뮬레이션 최적화
요구사항: 주어진 type(0=queue, 1=stack)과 초기 값들로 구성된 구조에 대해, 입력 m개를 순서대로 넣고 최종적으로 빠져나오는 값을 출력해야 한다.

사용 개념

자료구조
- Deque : 앞/뒤 삽입·삭제가 O(1)
알고리즘/기법
- 불필요한 시뮬레이션 제거
핵심 키워드
- queue만 결과에 영향
- 초기 queue 값의 “흐름”을 한 덩어리로 처리

풀이 아이디어 및 코드

방법 1 : 시뮬레이션 기반 풀이 (시간 초과로 실패)

전체를 매 입력마다 끝까지 시뮬레이션해서 m × n이 발생하는 구조라 시간 복잡도가 커진다.

Deque를 활용해 구현

//  queuestack

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        ArrayList<Deque<Integer>> arr = new ArrayList<>();
        String[] types = br.readLine().split(" ");
        String[] values = br.readLine().split(" ");

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        String num = "";
        String temp = "";
        for(int i = 0; i < m; i++){
            num = st.nextToken();
            for(int j = 0; j < n; j++){
                if(types[j].equals("0")){
                    temp =  values[j];
                    values[j] = num;
                    num = temp;
                } else {
                    continue;
                }
            }

            sb.append(num+" ");
        }
        System.out.println(sb);
    }
}

배열을 활용해 구현

//  queuestack

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        ArrayList<Deque<Integer>> arr = new ArrayList<>();
        int[] types = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");

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

        StringTokenizer st3 = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        for(int i=0;i<n;i++){
            arr.add(new ArrayDeque<>());
            types[i] = Integer.parseInt(st.nextToken());
            arr.get(i).add(Integer.parseInt(st2.nextToken()));
        }
        int num;
        for(int i = 0; i < m; i++){
            arr.get(0).add(Integer.parseInt(st3.nextToken()));
            for(int j = 0; j < n-1; j++){
                if(types[j] == 0){
                    num = arr.get(j).pollFirst();
                } else {
                    num = arr.get(j).pollLast();
                }
                arr.get(j+1).add(num);
            }

            if(types[n-1] == 0){
                num = arr.get(n-1).pollFirst();
            } else {
                num = arr.get(n-1).pollLast();
            }
            sb.append(num+" ");
        }
        System.out.println(sb);
    }
}

방법 2 : 관찰로 O(n+m) 만들기

stack(type=1)은 “넣고 바로 빼는 효과”만 내서 최종 출력 흐름에 남는 값이 없다.

queue(type=0)의 초기 값들만 결과 스트림에 영향을 준다.

따라서 초기 queue 값들을 한 번에 모아두고, 매 쿼리마다 입력값 push → 맨 앞 pop만 하면 된다.

핵심 로직 흐름
q = deque()

// 초기 상태에서 type=0(queue)인 값만 모음
for i in 0..n-1:
    if type[i] == 0:
        q.addLast(value[i])

// 실제 출력은 가장 "앞에서" 빠져나오므로,
// 위에서 모은 queue 값들의 순서를 "역방향"으로 맞춰야 한다.
// (구현에서는 q에 넣는 순서를 뒤에서부터 넣거나, 앞에 addFirst로 넣는다)

for each x in queries:
    q.addLast(x)
    print q.pollFirst()

Java 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] type = new int[n];
        int[] val = new int[n];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) type[i] = Integer.parseInt(st1.nextToken());

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) val[i] = Integer.parseInt(st2.nextToken());

        int m = Integer.parseInt(br.readLine());
        StringTokenizer st3 = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

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

        for (int i = n - 1; i >= 0; i--) {
            if (type[i] == 0) q.addFirst(val[i]);
        }

        for (int i = 0; i < m; i++) {
            int x = Integer.parseInt(st3.nextToken());
            q.addLast(x);
            sb.append(q.pollFirst()).append(' ');
        }

        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

시간 복잡도: O(n × m)
공간 복잡도: O(n)

방법 2

시간 복잡도: O(n + m)
공간 복잡도: O(n) (type=0인 값 개수만큼)

어려웠던 점

처음 실제 시뮬레이션 기반의 풀이에서 시간복잡도를 어떻게 더 줄여야 하는지 감이 잡히지 않았다.
매 쿼리마다 n개 구조를 끝까지 시뮬레이션하는 방식에서 병목이 생겼다.

배운 점 및 팁

전체를 그대로 시뮬레이션하지 말고, 출력에 실제로 영향을 주는 요소만 남기는 관찰이 핵심이다.
이 문제는 type=1(stack)이 결과 흐름에서 사라지는 요소라서, type=0(queue)만 모아 한 번에 처리하면 된다.
Deque로 addLast / pollFirst만 하면 쿼리당 O(1)로 끝난다.