[백준] 24511번 : queuestack Silver3(실버 3) - JAVA[자바]

[Silver III] queuestack - 24511

문제 링크

성능 요약

메모리: 88944 KB, 시간: 600 ms

분류

자료 구조, 덱, 큐, 스택

제출 일자

2023년 11월 23일 09:09:58

문제 설명

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

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

queuestack의 작동은 다음과 같다.

•  x0을 입력받는다.
•  x0을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x1이라 한다.
•  x1을 2번 자료구조에 삽입한 뒤 2번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x2이라 한다.
• ...
•  xN−1을 N번 자료구조에 삽입한 뒤 N번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 xN이라 한다.
•  xN을 리턴한다.

도현이는 길이 M의 수열 C를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 1 참고)

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

입력

첫째 줄에 queuestack을 구성하는 자료구조의 개수 N$N$이 주어진다. (1≤N≤100000$1 \leq N \leq 100\,000$)

둘째 줄에 길이 N의 수열 A가 주어진다. i번 자료구조가 큐라면 Ai=0, 스택이라면 Ai=1이다.

셋째 줄에 길이 N의 수열 B가 주어진다. Bi는 i번 자료구조에 들어 있는 원소이다. (1≤Bi≤1000000000)

넷째 줄에 삽입할 수열의 길이 M이 주어진다. (1≤M≤100000)

다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이 M$M$의 수열 C$C$가 주어진다. (1≤Ci≤1000000000)

입력으로 주어지는 모든 수는 정수이다.

출력

수열 C의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

 

 

1. 스택은 LIFO 구조로 방금 들어간 값이 방금 나온다 그러므로 스택은 큐 스택에서 신경쓰지 않아도 됨

2. 큐만 있다는 가정하에 원소를 추가하고 마지막 원소가 나오는 FIFO구조이다.

3. DEQUQ로 선언하면 편리하게 구현이 가능함

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> queue = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for(int i = 0; i < n;i++){
            arr[i] = Integer.valueOf(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            int tmp = Integer.parseInt(st.nextToken());
            if(arr[i] == 0){
                queue.offer(tmp);
            } 
        }
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++){
            int tmp = Integer.parseInt(st.nextToken());
            queue.offerFirst(tmp);
            sb.append(queue.pollLast() + " ");
        }
        System.out.println(sb.toString());
    }
}