[백준 알고리즘] 24511번: queuestack (JAVA)

 

https://www.acmicpc.net/problem/24511

 

소스코드

import java.io.*;
import java.util.*;
public class prac {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

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

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            queuestack[i] = Integer.parseInt(st.nextToken()); // 해당 인덱스의 자료구조가 큐인지 스택인지 
        }

        Deque<Integer> dq = new ArrayDeque<>(); // 값을 넣고 뺼 덱 생성 

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int k = Integer.parseInt(st.nextToken());
            if (queuestack[i] == 0) { // stack은 후입선출이라 넣었다 빼는 값이 같기 때문에 제외하고 큐만 취급
                dq.add(k);
            }
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int v = Integer.parseInt(st.nextToken());
            dq.addFirst(v);
            sb.append(dq.pollLast()).append(" ");
        }
        System.out.println(sb);
    }
}

 

---

풀이

★ 생각보다 어려웠던 문제였습니다 ! 처음엔 이중 for문을 사용해서 구현하였습니다. 그랬더니 시간 초과를 받았고, 입력 값 크기를 살펴보니 n과 m이 각각 100,000까지 들어올 수 있기 때문에 이중 for문을 사용하면 100억의 연산과정이 필요하게 됩니다 ! 

 

★ 큐는 선입선출의 구조를, 스택은 후입선출의 구조를 가지고 있습니다. 문제에서 주어진 조건을 확인해보면 stack의 경우엔 들어간 값이 바로 제거되기 때문에 굳이 고려해주지 않아도 됩니다 ! 그렇기에 queue 구조만 확인해주면 됩니다.