[ 백준 24511번 문제 ] queuestack - JAVA

 

이번 글에서는 큐, 스택에 마무리 문제인 24511번 문제를 해결해 보자.
시간 제한과 메모리 제한이 까다로울 것으로 예상된다.

 

 

문제 핵심

• 첫째 줄 - 자료구조의 수 : N
• 둘째 줄 - 수열의 종류 : 0 ( Queue ), 1 ( Stack )
• 셋째 줄 - 자료구조의 초기값 설정
• 넷째 줄 - 삽입할 수열의 길이 : M
• 다섯째 줄 - 삽입할 수열의 원소들

풀이 과정

첫 번째 예제의 과정 중 첫 번째 스텝을 다음과 같이 나타낼 수 있다.

그림 처럼 queue와 stack을 구현하여 값을 삽입하고 제거하는 과정으로 구현해보자. 

아마 메모리에서 먼저 초과되지 않을까 싶다.

 

 

1. 자료구조 저장

0, 1과 구별 값에 따라 큐인지 스택인지 구별하여 저장한다.

List<Object> dataStructure = new ArrayList<Object>();

for (int i = 0; i < N; i++) {
    int type = Integer.parseInt(stringTokenizer.nextToken());

    if (type == 0) {
        dataStructure.add(new LinkedList<Integer>());
    } else {
        dataStructure.add(new Stack<Integer>());
    }

}

 

2. 초기 값 저장

세번 째 줄의 초기 값들을 저장한다.

이 때 초기값들은 instanceof를 통해 자료구조를 판별 후 맞는 메소드를 사용한다.

for (int i = 0; i < N; i++) {
    int num = Integer.parseInt(stringTokenizer.nextToken());
    if (dataStructure.get(i) instanceof Queue) {
        ((Queue<Integer>) dataStructure.get(i)).offer(num);
    } else {
        ((Stack<Integer>) dataStructure.get(i)).add(num);
    }
}

 

3. 메인 과정

새로운 값 들이 큐와 스택을 지나면서 반복되는 과정이다.

이 때, 사실 스택이 값을 거쳐가기만 하기 때문에 의미가 없다.

for (int i = 0; i < M; i++) {
    int num = Integer.parseInt(stringTokenizer.nextToken());
    int temp = num;
    for (int j = 0; j < N; j++) {
        if (dataStructure.get(j) instanceof Queue) {
            ((Queue<Integer>) dataStructure.get(j)).add(temp);
            temp = ((Queue<Integer>) dataStructure.get(j)).remove();
        }
    }

    stringBuilder.append(temp).append(" ");

}

 

 

결과는 시간 초과로 메모리 문제가 아닌 2 중 for문에 N과 M의 최악의 경우 (On2)
100,000 * 100,000 = 10,000,000,000 기 때문에 벌어진 일이다.
그렇다면 2 중 for문의 구조를 제거하고,
스택구조에서 값은 지나치기만 하기 때문에 경우에서 제거한다.

 

4. 자료구조의 재구성

그렇다면 큐의 구조일 때 값을 교체하는 과정이고, 그게 여러개라면 하나씩 밀려나는 과정이다.

큐 여러개가 하나의 값만 가지고 있기 때문에 여러개의 큐가 하나의 큐가 되어버린다.

( 즉, 다음과 같은 구조일 때 새로운 값이 들어온다면 하나의 큐처럼 행동한다. )

그렇다면 하나의 큐를 생성하고 큐일 경우에만 값을 추가한다.

Deque<String> queue = new ArrayDeque<>();
StringBuilder stringBuilder = new StringBuilder();
int N = Integer.parseInt(bufferedReader.readLine());


String[] dataStructureString = bufferedReader.readLine().split(" ");
String[] valueString = bufferedReader.readLine().split(" ");
for (int i = 0; i < N; i++) {
    int type = Integer.parseInt(dataStructureString[i]);
    if(type == 0){
        queue.addLast(valueString[i]);
    }
}

 

5. 메인 과정 재구성

다음과 같이 큐의 삽입과 삭제를 반복하면 O(n)의 경우의 수와 메모리 문제가 모두 해결된다.

int M = Integer.parseInt(bufferedReader.readLine());
String[] addValueString = bufferedReader.readLine().split(" ");

for (int i = 0; i < M; i++) {
    queue.addFirst(addValueString[i]);
    stringBuilder.append(queue.removeLast()).append(" ");
}

 

이번 문제는 마치 알고리즘이 큐처럼 행동하게 하여 해결할 수 있었다.
다음과 같이 자료구조의 개념을 이해한다면 여러방법으로 구현할 수 있다.
줄 서거나(큐), 박스에 물건을 넣고 빼거나(스택) 처럼 한 가지로 제한되지 않는다는 점이다.

시간과 메모리를 줄여야 한다는 점에서 이런 구조를 생각할 수 있었던 문제였다.

 

실패 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        List<Object> dataStructure = new ArrayList<Object>();
        StringTokenizer stringTokenizer;
        StringBuilder stringBuilder = new StringBuilder();
        int N = Integer.parseInt(bufferedReader.readLine());

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for (int i = 0; i < N; i++) {
            int type = Integer.parseInt(stringTokenizer.nextToken());

            if (type == 0) {
                dataStructure.add(new LinkedList<Integer>());
            } else {
                dataStructure.add(new Stack<Integer>());
            }

        }

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            if (dataStructure.get(i) instanceof Queue) {
                ((Queue<Integer>) dataStructure.get(i)).offer(num);
            } else {
                ((Stack<Integer>) dataStructure.get(i)).add(num);
            }
        }

        int M = Integer.parseInt(bufferedReader.readLine());

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            int temp = num;
            for (int j = 0; j < N; j++) {
                if (dataStructure.get(j) instanceof Queue) {
                    ((Queue<Integer>) dataStructure.get(j)).add(temp);
                    temp = ((Queue<Integer>) dataStructure.get(j)).remove();
                }
            }

            stringBuilder.append(temp).append(" ");

        }

        System.out.println(stringBuilder);
    }
}

성공 전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        Deque<String> queue = new ArrayDeque<>();
        StringBuilder stringBuilder = new StringBuilder();
        int N = Integer.parseInt(bufferedReader.readLine());


        String[] dataStructureString = bufferedReader.readLine().split(" ");
        String[] valueString = bufferedReader.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            int type = Integer.parseInt(dataStructureString[i]);
            if(type == 0){
                queue.addLast(valueString[i]);
            }
        }

        int M = Integer.parseInt(bufferedReader.readLine());
        String[] addValueString = bufferedReader.readLine().split(" ");

        for (int i = 0; i < M; i++) {
            queue.addFirst(addValueString[i]);
            stringBuilder.append(queue.removeLast()).append(" ");
        }
        System.out.println(stringBuilder);
    }
}