[JAVA] 백준 24511. queuestack

이 글은 읽는데 약 6분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

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

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

queuestack의 작동은 다음과 같다.

  • \(x_0\)을 입력받는다.
  •  \(x_0\)을 \(1\)번 자료구조에 삽입한 뒤 \(1\)번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 \(x_1\)이라 한다.
  •  \(x_1\)을 \(2\)번 자료구조에 삽입한 뒤 \(2\)번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 \(x_2\)이라 한다.
  • …
  • \(x_{N-1}\)을 \(N\)번 자료구조에 삽입한 뒤 \(N\)번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 \(x_N\)이라 한다.
  • \(x_{N}\)을 리턴한다.

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

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

입력

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

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

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

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

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

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

출력

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

큐스택의 이해

문제를 처음 봤을 때 설명이 복잡해서 두 번 읽었다. 그리고도 모자라서 종이에 그려보면서 파악했다.
결론적으로 말하면 큐스택이란 한 개의 원소를 가지는 큐 또는 스택의 배열 정도로 이해하면 될 것 같다.

처음에는 숫자 한 개를 큐스택에 넣으면 첫 번째 큐 또는 스택에서 숫자를 추가한 후 pop한다. 이후에는 pop된 값을 다음 큐 또는 스택에 넣고 pop하기를 반복하며, 마지막에서 pop된 숫자를 출력한다.

수열로 넣을 숫자가 여러개 주어지며, 하나의 숫자를 큐스택에 통과시킨 후 큐스택은 따로 값을 변경하지 않고 그 상태에서 바로 다음 숫자를 넣는다.

작동 방식을 영상으로 한 번 이해해보자.

보다시피 숫자가 주어지면 해당 숫자를 첫 번째 큐 또는 스택에 넣은 후 하나를 꺼낸다(pop).
당연하지만 큐의 경우에는 선입선출로 숫자를 넣으면 기존에 있던 숫자가 pop되며, 스택은 후입선출로 넣은 숫자가 다시 나와 사실상 숫자를 넣는 의미가 없다.

이걸 반복해서 마지막에 pop된 값을 출력에 추가하는 것이다.

풀이

큐스택의 처음 값부터 위 예시 영상에서 숫자를 순서대로 넣을 때 각 숫자가 통과하고난 후의 값을 순서대로 나열하면 아래와 같다.

[1 2 3 4]
c=6 [6 1 3 2] => 4
c=8 [8 6 3 1] => 2
c=5 [5 8 3 6] => 1

제일 처음과 제일 마지막만 두고 비교하면 결국 숫자를 앞에 추가하고 뒤의 숫자가 빠지는 모습이다.
즉, 마치 큐스택 자체는 덱과 같은 모습이며, 주어진 수열 C의 각 숫자를 앞에 추가하고, 뒤는 빼서 출력에 추가하는 식으로 코드를 짜면 된다.

또한 어차피 스택의 경우에는 넣고 빼면 들어간 숫자가 그대로 다시 나와 값에는 변화가 없으니 큐를 만들 때 무시해도 될 것이다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

int N = Integer.parseInt(br.readLine());
String[] flags = br.readLine().split(" ");
String[] nums = br.readLine().split(" ");
int M = Integer.parseInt(br.readLine());
String[] C = br.readLine().split(" ");

Deque<Integer> qs = new ArrayDeque<>();  // 큐스택을 그냥 하나의 덱으로 취급

for(int i=0; i<N; i++){
    if(flags[i].equals("0")){  // 큐일 경우에만 추가한다. 스택은 어차피 값에 변화가 없으니
        qs.addLast(Integer.parseInt(nums[i]));  // 일단 주어진 숫자들을 순서대로 추가
    }
}


for(int i=0; i<M; i++){  // 수열 C의 숫자 개수만큼 반복
    int c = Integer.parseInt(C[i]);  // 이번에 넣을 숫자

    qs.addFirst(c);  // 큐스택(이지만 사실은 덱)의 제일 앞에 추가하고
    sb.append(qs.pollLast()).append(" ");  // 큐스택의 제일 뒷 값을 출력에 추가
}


System.out.println(sb.toString());
br.close();

이러한 규칙만 알면 생각보다 쉬운 문제이다.

댓글