백준 - [Silver III] queuestack - 24511 (java)

문제 설명

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

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

queuestack의 작동은 다음과 같다.

•  x0x0을 입력받는다.
•  x0x0을 11번 자료구조에 삽입한 뒤 11번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x1x1이라 한다.
•  x1x1을 22번 자료구조에 삽입한 뒤 22번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x2x2이라 한다.
• ...
•  xN−1xN−1을 NN번 자료구조에 삽입한 뒤 NN번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 xNxN이라 한다.
•  xNxN을 리턴한다.

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

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

입력

첫째 줄에 queuestack을 구성하는 자료구조의 개수 NN이 주어진다. (1≤N≤1000001≤N≤100000)

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

셋째 줄에 길이 NN의 수열 BB가 주어진다. BiBi는 ii번 자료구조에 들어 있는 원소이다. (1≤Bi≤10000000001≤Bi≤1000000000)

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

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

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

출력

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

 

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

public class Main {
    
    public static void main(String [] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

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

        Deque<Integer> deque = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<n ; i++){
            int num = Integer.parseInt(st.nextToken());
            if(isStack[i] == 0){
                deque.offerLast(num);
            }
        }

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

 

문제를 이해하는데 꽤 오래 걸림 .. 

그리고 시간초과를 3번을 경험하고야 풀었다죠 .. 

ㅋㅋㅋ 

스택일때는 아무일도 일어나지 않는 다는 것만 

이해하면 될듯 ! 

큐일때만 넣어주고 빼주고 .. !!!