📌 문제

[24511] queuestack

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 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 100\,000$)

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

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

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

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

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

⬆️ 출력

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

💡 코드

❓ 문제만 읽어서는 도저히 이해가 안돼서 직접 노가다 해본 후에 겨우 이해했다 ^^,, 요약하자면 n개의 큐/스택을 생성하여 수열 a의 요소들을 각 큐/스택에 차례대로 하나씩 넣고, b 수열의 요소들을 하나씩 넣고 빼고 넣고 빼고...를 반복해주면 되는 문제였다!

⏱️ 예제의 설명에 나온 것처럼 questack을 하나의 배열로 생각하고 문제를 풀어보았다. n개의 자료구조가 큐인지 스택인지 구분하기 위한 변수를 check[]에 저장하고, questack[]에 수열 A의 요소들을 순서대로 저장한다.

다음으로 수열 B의 크기와 요소들을 입력받아 수열 B의 요소들을 순서대로 x에 담아 n개의 자료구조에 삽입/삭제 과정을 반복한다. 위 문제 풀이를 보면 n번째 자료구조가 큐인 경우에는 선입선출에 따라 원래 저장되어있던 값을 꺼내고, 스택인 경우에는 후입선출에 따라 삽입한 값을 바로 꺼낸다.

따라서, 큐/스택 구분 변수인 check[n]이 0으로 큐인 경우에는 questack[n]에 삽입한 x 값을 넣고 questack[n]에 원래 저장되어있던 값을 꺼내 x에 저장하고, 스택인 경우에는 어차피 넣은 값을 다시 꺼내야하므로 x를 그대로 가져가면 된다. 해당 과정을 n번 반복하여 마지막 x를 출력한다.

해당 코드를 이클립스에서 실행하면 제대로 출력이 되지만, 백준에 제출하면 시간 초과가 뜬다,, 아무래도 이중 for문에서 시간을 많이 잡아먹은 것 같다,, (어떻게 보면 당연함,, 10만 * 10만 = 100억임,,)

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		int[] questack = new int[n]; // 큐스택
		
		String[] check = br.readLine().split(" "); // 큐/스택 구분
		StringTokenizer st = new StringTokenizer(br.readLine()); // 수열 A
		for(int i=0;i<n;i++) {
			questack[i] = Integer.parseInt(st.nextToken());
		}
		
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine()); // 수열 b
		
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<m;i++) {
			int x = Integer.parseInt(st.nextToken());
			
			for(int j=0;j<n;j++) {
				int tmp = 0;
				
				if(check[j].equals("0")) {
					tmp = x;
					x = questack[j]; questack[j] = tmp;
				}
			}
			sb.append(x + " ");
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}

✅ 이중 for문을 없애려면 questack을 for문을 사용하지 않고 처리해줘야 하기 때문에, 인덱스를 사용해야 하는 배열 대신 다른 자료구조를 사용해줘야 한다. 그런데 다른 자료구조를 사용하더라도 check[]를 통해 n번째 자료구조가 큐/스택인지 판별하기 위해서는 여전히 for문이 필요하다.

이를 해결하기 위해 위 풀이를 참고해보면 스택인 경우에는 x를 넣었다가 바로 꺼내기 때문에 questack에 변화를 주지 않는다. 그렇다면, 처음 questack에 값을 저장할 때, 없어도 딱히 영향을 미치지 않는 스택의 값을 빼고, 큐의 값만 저장하면 이중 for문을 사용하지 않고 해결할 수 있다!
수열 b의 한 요소 x0을 삽입한 후 최종 questack은 [x0, (기존) 1번째 요소, 2번째 요소, ..., n-1번째 요소] 형태이고, 기존 questack의 가장 뒤에 있던 값을 리턴한다.

즉, 번거롭게 이중 for문을 돌릴 필요 없이, 양방향 삽입/삭제가 가능한 덱을 사용하여 삽입한 값 x0을 questack의 가장 앞에 넣고(offerFirst()), 기존 questack의 가장 뒤에 있는 값을 꺼낸 후 출력해주면 된다! (pollLast())

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		String[] check = br.readLine().split(" "); 
		Deque<Integer> questack = new LinkedList<>();
		
		StringTokenizer st = new StringTokenizer(br.readLine()); // 수열 a
		for(int i=0;i<n;i++) {
			int num = Integer.parseInt(st.nextToken());
			if(check[i].equals("0")) questack.offer(num); // 큐만 저장
		}
		
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine()); // 수열 b
		
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<m;i++) {
			questack.offerFirst(Integer.parseInt(st.nextToken()));
			sb.append(questack.pollLast() + " ");
		}
		bw.write(sb + "");
 		
		br.close();
		bw.close();
	}
}