[백준] 24511번 : queuestack (스택/큐 실버Ⅲ) - Java

문제

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

24511번: queuestack

문제

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

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

queuestack의 작동은 다음과 같다.

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

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

입력

출력

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

예제 입력 1

4
0 1 1 0
1 2 3 4
3
2 4 7

예제 출력 1 

4 1 2

각 상태에 대한 큐스택 내부를 표현하면 다음과 같다.

• 초기 상태 : [1, 2, 3, 4]
• 첫 번째 원소 삽입 : [2, 2, 3, 1]
• 두 번째 원소 삽입 : [4, 2, 3, 2]
• 세 번째 원소 삽입 : [7, 2, 3, 4]

예제 입력 2

5
1 1 1 1 1
1 2 3 4 5
3
1 3 5

예제 출력 2 

1 3 5

접근

아 이거 문제가 ... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

푸는 것 보다 처음에 문제 이해하는게 조금 난해했다.. 한 세 번 읽고 이해한 듯

예제1로 문제를 다시 살펴보면

4
0 1 1 0
1 2 3 4
3
2 4 7

• N = 4 -> 자료구조 4개
• 두번째줄 0 1 1 0 -> 각 자료구조의 종류 
• 셋째 줄 1 2 3 4 -> 현재 각 자료구조에 들어있는 수
• 넷째 줄 -> 넣을 수의 갯수
• 마지막 줄 2 4 7 -> 넣을 수

이고, 첫 상태를 표로 나타내면

x = 2, 4, 7	형태	현재 요소
1번 자료구조	0 : 큐	1
2번 자료구조	1 : 스택	2
3번 자료구조	1  : 스택	3
4번 자료구조	0  : 큐	4

상태이다.

그리고 삽입을 진행하면,

1. x₀ = 2를 삽입
   1번 자료구조는 큐이므로 삽입 -> [1,2] , pop 하면 [2]이 되어 x = 1로 바뀐다. 이게 x₁가 된다.
   

   x₀ = 2 -> x₂ = 1	형태	현재 요소
   1번 자료구조	0 : 큐	1 ->2
   2번 자료구조	1 : 스택	2
   3번 자료구조	1  : 스택	3
   4번 자료구조	0  : 큐	4

2. x₂ = 1 을 삽입
   스택은 삽입 후 pop 하면 삽입된 값이 그대로 나오므로 변화가 없다. 따라서 x₂ = 1 로 그대로다.
   

   x₂ = 1 -> x₂= 1	형태	현재 요소
   1번 자료구조	0 : 큐	2
   2번 자료구조	1 : 스택	2 (그대로)
   3번 자료구조	1  : 스택	3 (그대로)
   4번 자료구조	0  : 큐	4

3.  x₂ = 1 을 삽입
   마찬가지로 그대로, x₃ = 1
   

   x₂ = 1 -> x₃ = 1	형태	현재 요소
   1번 자료구조	0 : 큐	1
   2번 자료구조	1 : 스택	2
   3번 자료구조	1 : 스택	3
   4번 자료구조	0  : 큐	4

4. x₃ = 1 삽입
   삽입 -> [1, 4] / pop -> [1] , x₄ = 4 가 되어 이를 출력하고 자료구조의 형태는 아래와 같은 상태
   

   x = 4, 7	형태	현재 요소
   1번 자료구조	0 : 큐	2
   2번 자료구조	1 : 스택	2
   3번 자료구조	1  : 스택	3
   4번 자료구조	0  : 큐	4 -> 1

5. 그리고 이 상태의 자료구조에서 남은 4, 7에 대해 1~4를 반복하면 된다.

결국 스택일 때는 아무일이 일어나지 않으므로, 큐일 경우에만 기존 요소를 갱신하고, 뽑아내주면 된다. 

생각보다 더 간단한 문제였다는 거..

풀이

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 reader = new BufferedReader(new InputStreamReader(System.in));
        // 1. 입력값 받아오기
        int N = Integer.parseInt(reader.readLine());

        int[] listQueuestack = new int[N];
        int[] currentList = new int[N];

        StringBuilder answer = new StringBuilder();
        // 1번 리스트 - 자료구조의 형태
        StringTokenizer input1 = new StringTokenizer(reader.readLine());
        for (int i = 0; i < N; i++) {
            listQueuestack[i] = Integer.parseInt(input1.nextToken());
        }
        // 2번 리스트 - 자료구조의 요소
        StringTokenizer input2 = new StringTokenizer(reader.readLine());
        for (int i = 0; i < N; i++) {
            currentList[i] = Integer.parseInt(input2.nextToken());
        }

        int M = Integer.parseInt(reader.readLine());
        int[] insertList = new int[M];
        // 3번 리스트 - 입력값 리스트
        StringTokenizer st3 = new StringTokenizer(reader.readLine());
        for (int i = 0; i < M; i++) {
            insertList[i] = Integer.parseInt(st3.nextToken());
        }
        // 큐 생성
        Deque<Integer> queue = new ArrayDeque<>();
        // 자료구조의 형태가 큐라면,
        for (int i = 0; i < N; i++) {
            if (listQueuestack[i] == 0) {
                queue.addFirst(currentList[i]); // 새로 만든 큐에 현재 요소를 담는다.
            }
        }
        for (int i = 0; i < M; i++) {
            queue.add(insertList[i]);
            answer.append((queue.pollFirst() + " "));
        }

        System.out.println(answer);
        reader.close();
    }
}