(JAVA)백준 문제 풀이 - 스택, 큐, 덱 단계 - 24511번 queuestack (실버 3)

이번 문제는 덱을 이용하여 스택과 큐가 혼합된 자료구조에 배열이 입력되었을때 출력 값을 구하는 문제이다.

문제를 이해하는데 꽤 애를 먹었는데 각각의 자료구조에 한 개의 원소가 들어있다라는 문구를 제대로 이해하지 못해서 처음에는 입력받은 자료구조의 배열을 통과하면서 스택과 큐로 변형되는 문제인줄 알았다가 예시를 한참 보고서야 제대로 이해할 수 있었다.

---

문제부터 이해하자!

예시를 잘 살펴보면서 문제를 이해해보자.

첫번째 예시에서 자료구조는 [큐,스택,스택,큐]의 구조로 이루어진다.

그리고 통과할 배열은 [1,2,3,4]로 이루어져있다.

나는 처음에 초기 상태를 보고 첫번째에는 2라는 입력값이 큐로 한번 통과하여 [2,3,4,2]로 나오고 그다음 출력된 1을 스택으로 통과시켜 [2,3,4,2]로 나오게 하여 배열의 마지막까지 순회한 후 마지막 원소를 출력하는 것으로 이해했는데 전혀 틀리게 이해하고 있었다.

문제를 잘 보면 각 자료구조의 원소는 1개라고 되어있는데 예제에서는 [1,2,3,4]로 표시했지만 실제로는 [1],[2],[3],[4]라는 4개의 자료구조를 통과하는 것이다.

따라서 순서는 다음과 같다.

1. 첫번째 입력값인 2가 첫번째 자료구조를 통과한다.
2. 첫번째 자료구조는 큐이므로 입력은 [1,2]로 된 후 FIFO에 따라 1이 반환된다.
3. 반환된 1을 두번째 자료구조에 입력한다.
4. 두번째 자료구조는 스택이므로 [2,1]로 된 후 LIFO에 따라 1이 반환된다.
5. 3번째 자료구조 역시 스택이므로 [3,1]로 된 후 1이 반환된다.
6. 마지막 자료구조는 큐이므로 [4,1]이 된 후 4가 반환된다.
7. 자료구조를 모두 통과하였으므로 4를 출력한다.

문제를 이해하였으니 코딩을 시작하자!

---

중요한 것은 효율성!

처음 문제를 풀때는 문제의 로직을 그대로 적용하였기 때문에 다음과 같이 구현하였다.

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

class Main{
    public static int n,k;
    public static String s;
    public static String[] str, std, input;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        std = br.readLine().split(" ");
        str = br.readLine().split(" ");
        k = Integer.parseInt(br.readLine());
        input = br.readLine().split(" ");
        Deque<String> arr = new ArrayDeque<>();

        for(int i = 0; i < k; i++){
            s = input[i];
            arr.offerFirst(s);
            for(int j = 0; j < std.length; j++){
                if(std[j].equals("1")){
                    arr.offerFirst(str[j]);
                    str[j] = arr.pollFirst();
                } else {
                    arr.offerFirst(str[j]);
                    str[j] = arr.pollLast();
                }
            }
            sb.append(arr.pollFirst()).append(" ");
        }

        System.out.println(sb.toString());
    }
}

입력받은 값을 전부 저장한 후 덱을 선언한다.

비어있는 덱에 첫번째 입력값을 넣어 준 후 반복문을 순회하며 자료구조를 확인한다.

1이면 스택처럼 작동하여야 하기 때문에 배열의 앞으로 값을 넣어주고 (이미 입력값이 있기 때문에 스택처럼 작동하려면 앞으로 배열값을 넣어주어야 한다) 맨앞의 요소를 원래 배열에 넣어준다.

0이면 큐처럼 작동시키기 위하여 앞에 배열 값을 넣고 마지막 값을 반환하여 원래 배열에 넣어준다.

그렇게 되면 덱에 남은 요소가 마지막 출력값이기 때문에 해당 요소를 StringBuilder에 넣고 출력하면 된다.

 

테스트를 몇번 돌려보고 정상 출력되기에 제출을 해보았으나...

나는 2중 for문을 사용하였기 때문에 O(n2)의 시간복잡도를 가진다.

for문의 각 최대값은 100,000 * 1,000,000,000이므로... 당연히 1초를 넘기는 것인데 제한사항을 미리 체크하지 못했다.

 

시간을 줄이기 위해선 단일 for문으로 바꿀 필요성이 있었는데 그러기 위해서는 큐와 스택일때를 분리해서 생각하여야했다.

그렇다면 스택 구조를 건너뛰어도 상관없는가??가 중요한 포인트였는데...

결과적으로 이 문제는 입출력이 거꾸로 되는 큐를 구현하는 문제라고 생각해도 무방하다.

눈치가 빠른 사람은 이미 알았겠지만 스택구조의 경우 입력된 값을 그대로 반환한다.

(즉, 어차피 입력값을 그대로 넘기기 때문에 로직에서 빠져도 무방하다)

 

그러면 앞서 보았던 예제를 큐만 적용하여서 다시 살펴보자.

우선 자료구조가 큐인것은 1,4이기 때문에 초기 상태를 [1,4]로 가정한다.

1. 입력값인 2가 첫 자료구조를 통과한다.
2. [1,2]로 입력되어 1이 반환된다.
3. 두번째 자료구조는 [4,2]가 되기때문에 4가 반환된다.
4. 전체 구조는 [1,4]에서 [2,1]로 바뀐다.

전체적인 관점에서 보면 전체 자료구조가 마지막에 입력된 값이 제일 처음으로 오고 제일 마지막 값이 반환되는 것을 알 수 있다.

그럼 위의 로직대로 코드를 수정하여 보자.

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

class Main{
    public static int n,k;
    public static String s;
    public static String[] str, std, input;
    public static StringBuilder sb = new StringBuilder();
    public static StringTokenizer st;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        str = br.readLine().split(" ");
        Deque<Integer> arr = new ArrayDeque<>();
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            if (str[i].equals("0")) {
                arr.offerLast(Integer.parseInt(st.nextToken()));
            } else {
                st.nextToken();
            }
        }

        k = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < k; i++) {
            if (arr.isEmpty()) {
                sb.append(st.nextToken()).append(" ");
            } else {
                arr.offerFirst(Integer.parseInt(st.nextToken()));
                sb.append(arr.pollLast()).append(" ");
            }
        }

        System.out.println(sb.toString());
    }
}

결과적으로 단일 for문을 사용하여 시간을 줄일 수 있었다.

구현 자체는 그렇게 어렵지 않았는데 문제를 정확하게 이해하고 어떻게 빠르게 만들것인가에 시간이 오래 소요되었던 문제였다.