24511. queuestack

 

문제

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

queuestack의 구조는 다음과 같다. 1번, 2번, ... , 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이 주어진다. (1 ≤ N ≤ 100,000)

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

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

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

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

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

출력

 

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

 

 

나의 풀이(시간 초과)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		try {
			int n = Integer.parseInt(br.readLine());
			String[] arrType = br.readLine().split(" ");

			String[] firstE = br.readLine().split(" ");
			int m = Integer.parseInt(br.readLine());
			String[] insertE = br.readLine().split(" ");
			Map<String, Object> dataStructures = new HashMap<>();
			for (int i = 0; i < n; i++) {
				int dType = Integer.parseInt(arrType[i]);
				int e0 = Integer.parseInt(firstE[i]);
				if (dType == 0) {
					Queue<Integer> queue = new LinkedList();
					queue.add(e0);
					dataStructures.put("ds" + i, queue);
				} else if (dType == 1) {
					ArrayList<Integer> stack = new ArrayList<>();
					stack.add(e0);
					dataStructures.put("ds" + i, stack);
				}
			}
			int elem = -1;
			for (int i = 0; i < m; i++) {
				elem = Integer.parseInt(insertE[i]);
				for (int j = 0; j < n; j++) {
					int dType = Integer.parseInt(arrType[j]);
					String key = "ds" + j;
					if (dType == 0) {
						Queue<Integer> receivedQueue = (Queue<Integer>) dataStructures.get(key);
						receivedQueue.add(elem);
						elem = receivedQueue.remove();
					} else if (dType == 1) {
						ArrayList<Integer> receivedStack = (ArrayList<Integer>) dataStructures.get(key);
						receivedStack.add(elem);
						elem = receivedStack.get(receivedStack.size() - 1);
						receivedStack.remove(receivedStack.size() - 1);
					}
				}
				bw.write(String.valueOf(elem));
				if (i < m - 1) {
					bw.write(" ");
				}
			}
			bw.flush();
			bw.close();
			br.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}

}

 

자료구조가 Queue일 경우만 값이 뒤바뀐다는 걸 깨닫고 깎고 깎아서 만든

두 번째 풀이(시간 초과)

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class javaStudy10 {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder output = new StringBuilder();

        try {
            int n = Integer.parseInt(br.readLine());
            String[] arrType = br.readLine().split(" ");
            String[] firstE = br.readLine().split(" ");
            int m = Integer.parseInt(br.readLine());
            String[] insertE = br.readLine().split(" ");

            int[] list = new int[n];
            int[] dType = new int[n];

            // 배열 초기화
            for (int i = 0; i < n; i++) {
                list[i] = Integer.parseInt(firstE[i]);
                dType[i] = Integer.parseInt(arrType[i]);
            }

            int elem = -1;

            // 삽입 및 처리
            for (int i = 0; i < m; i++) {
                elem = Integer.parseInt(insertE[i]);
                for (int j = 0; j < n; j++) {
                    if (dType[j] == 0) { // Queue일 때
                        int tmp = elem;
                        elem = list[j];
                        list[j] = tmp;
                    }
                }
                output.append(elem);
                if (i < m - 1) {
                    output.append(" ");
                }
            }

            // 출력
            bw.write(output.toString());
            bw.flush();
            bw.close();
            br.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

 

 

최종 풀이

와.... 알았다. 이 문제의 알고리즘은 결국 덱이었다.

1. 문제에선 큐, 스택 등 자료구조를 얘기하지만, 결국 자료구조의 길이가 1이기 때문에, 결국 "큐"일 경우에"만" 숫자끼리 자리를 바꾼다는 것

2. 그러면 결국 자료형태가 "큐"인 것들만 모아서 숫자끼리 자리바꿈을 하면 되는데, 이걸 전체 순회로 하면 또 시간초과가 난다. 그런데 풀다 보면 반드시 "큐"인 값들의 마지막 값을 리턴으로 받는 걸 알 수 있다. 그리고 "큐"인 값들의 맨 첫번째 값은 당연히 입력값이 들어간다.

3. 2번을 힌트로 몇 번 예시를 그려 보면, 결국 큐스택 문제는 addFirst로 입력값을 덱에 넣고, removeLast로 마지막 값을 지우면서 리턴받는 덱의 구조였음을 깨닫게 된다! 그리고 마침내 시간초과 안 나고 문제 해결....!!!!!!!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder output = new StringBuilder();

		try {
			int n = Integer.parseInt(br.readLine());
			String[] arrType = br.readLine().split(" ");
			String[] firstE = br.readLine().split(" ");
			int m = Integer.parseInt(br.readLine());
			String[] insertE = br.readLine().split(" ");
			Deque<Integer> deque = new ArrayDeque();
			int[] list = new int[n];
			int[] dType = new int[n];

			// 배열 초기화
			for (int i = 0; i < n; i++) {
				list[i] = Integer.parseInt(firstE[i]);
				dType[i] = Integer.parseInt(arrType[i]);
			}
			// 큐가 되는 값만 만든 다음
			for (int i = 0; i < dType.length; i++) {
				if (dType[i] == 0) {
					deque.add(list[i]);
				}
			}
			
			int elem = -1;

			// 삽입 및 처리
			for (int i = 0; i < m; i++) {
				elem = Integer.parseInt(insertE[i]);
				deque.addFirst(elem);
				elem = deque.removeLast();
				output.append(elem);
				if (i < m - 1) {
					output.append(" ");
				}
			}

			// 출력
			bw.write(output.toString());
			bw.flush();
			bw.close();
			br.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

 

이 풀이의 특기할 점은, 심지어 챗gpt조차도 이 풀이를 안 내줬다는 것이다. 결국 알고리즘을 깎고 깎다 보면 더 효율적인 것들은 항상 있다. 수학 잘하시는 분들, 알고리즘 하시는 분들 전부 존경한다...!