[P&B] #109 BAEKJOON 24511

백준 24511번 queuestack JAVA

문제 설명

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 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에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다.

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

 

입력

첫째 줄에 queuestack을 구성하는 자료구조의 개수 N이 주어진다. (1 <= N <= 100,000)

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

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

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

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

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

 

출력

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

 

나의 문제 풀이 코드

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

public class bj24511 {
    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()); // N: 자료구조의 개수

        int[] typeArr = new int[N]; // 각 자료구조의 타입(0: 큐, 1: 스택)을 저장하는 배열

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 각 자료구조의 타입 정보를 입력받아 typeArr에 저장
        for (int i = 0; i < N; i++) {
            typeArr[i] = Integer.parseInt(st.nextToken());
        }

        Deque<Integer> deque = new ArrayDeque<>(); // 원소를 저장하기 위한 Deque 자료구조

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());

            // 현재 자료구조가 큐인 경우 뒤에 원소를 삽입
            if (typeArr[i] == 0) {
                deque.addLast(num);
            }
        }

        int M = Integer.parseInt(br.readLine()); // M: 삽입할 원소의 개수

        st = new StringTokenizer(br.readLine());
        br.close();

        // 원소를 삽입하고 리턴값을 구하는 과정을 반복
        while (M --> 0) { // M을 하나씩 감소하며 반복
            int moveValue = Integer.parseInt(st.nextToken()); // 삽입할 원소

            deque.addFirst(moveValue); // 현재 자료구조에 원소를 삽입
            sb.append(deque.pollLast()).append(" "); // 마지막 자료구조에서 원소를 빼고 결과 문자열에 추가
        }

        System.out.println(sb); // 결과 문자열 출력
    }
}

 

문제 풀이 코멘트

queuestack 자료구조를 구현하고, 주어진 수열에 따라 이 자료구조에 값을 넣고 빼면서 원하는 결과를 출력하는 프로그램입니다. 

 각 자료구조의 타입(0 또는 1)을 저장할 배열 typeArr를 생성하여 각 자료구조의 타입(0 또는 1)을 입력 받고, typeArr에 저장합니다.
 그 다음, 데크 자료구조 deque를 생성합니다. 이 자료구조는 큐(Queue)와 스택(Stack)의 특성을 모두 가지고 있어서 queuestack을 구현하는 데 사용됩니다. 이 자료구조에 들어가는 원소를 입력 받을 때 해당 자료구조가 큐(0)인 경우, 원소를 데크의 뒤(addLast())에 추가합니다. 스택은 들어가자마자 나오기 때문에 자료형이 큐인 것만 저장합니다.

 이제 주어진 수열을 하나씩 처리합니다. 수열의 각 원소를 moveValue에 저장하고, 이를 데크의 앞(addFirst())에 추가합니다. 데크의 뒤에서 원소를 하나 꺼내서(pollLast()) sb에 추가하고, 출력 형식에 맞게 공백을 덧붙입니다.

 이렇게 코드는 주어진 조건에 따라 큐와 스택을 사용하여 값을 넣고 빼면서 최종 결과를 출력합니다. 자료구조를 활용하여 입력과 출력을 효율적으로 처리하고 있으며, 주어진 조건을 만족시키는 동작을 수행하고 있습니다.

 

 이 문제 역시 처음 푼 코드는 시간 초과가 발생하여 테스트를 통과하지 못했습니다. 처음 푼 코드의 경우 배열 structure를 사용하여 각 자료구조의 유형을 저장하고, elements 리스트에 각 자료구조에 들어있는 원소를 저장했습니다. 수열을 처리할 때 각 자료구조에 대한 조건을 확인하여, 해당 자료구조에 값을 추가하거나 스택의 경우에는 마지막 자료구조에 값을 추가했고, elements 리스트를 이용하여 각 자료구조에 대한 처리를 하며, 필요한 경우에는 원소를 추가하거나 제거했습니다. 제가 처음에 짠 코드는 위의 정답 코드와 기본적인 로직은 동일하게 동작하지만, 시간초과 문제가 발생하는 이유는 코드의 구현 방식과 데이터 구조의 차이 때문입니다.

 정답 코드에서는 큐와 스택을 결합한 데크(Deque)를 사용하여 큐의 특성과 스택의 특성을 모두 구현하는 데이터 구조를 가집니다. 따라서 큐에 원소를 추가하고 제거하는 연산이 빠르게 수행됩니다. 뿐만아니라 Deque를 사용하여 원소를 추가하고 제거하는 연산이 빠르게 수행됩니다.

 이에 반해 처음 푼 코드에서는 배열과 리스트를 사용하여 각 자료구조에 대한 원소를 저장하고 처리합니다. 원소 추가 및 제거 시에 리스트를 조작하므로 시간이 더 걸렸습니다. ArrayList의 add 및 remove 메서드를 사용하여 원소를 추가하고 제거하는데, 이 연산들은 원소를 추가하고 제거할 때마다 배열의 복사 작업이 필요하므로 시간이 더 많이 소요되었습니다.

 

시간복잡도를 어떤 자료구조를 사용하여 최적화 하느냐가 문제의 난이도가 높아지면서 중요해지는 것 같습니다.