[백준] 24511번 : queuestack (Java)

https://www.acmicpc.net/problem/24511

최근에 스택, 큐, 덱 단계에 새 문제가 추가되었다.

 

멈춰..

간단해보여서 설명처럼 queue와 stack이 랜덤하게 들어있는 배열을 만들면 될거라 생각하고 빨리 풀고 끝내려고 했는데 계속 시간초과가 뜬다.

 

---

처음에는 문제 설명 그대로 ArrayList에 LinkedList를 넣고, LinkedList에 값을 넣고 빼주는 작업을 모두 진행했다.

아마 시간복잡도는 O(N + M * N * 2N) ..?

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(bufferedReader.readLine());
        ArrayList<LinkedList> queuestack = new ArrayList();
        int[] isStack = new int[N];

        StringTokenizer isQueueOrStack = new StringTokenizer(bufferedReader.readLine());
        StringTokenizer line = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            LinkedList<Integer> inObject = new LinkedList<>();
            inObject.add(Integer.parseInt(line.nextToken()));
            queuestack.add(i, inObject);
            isStack[i] = Integer.parseInt(isQueueOrStack.nextToken());
        }

        int M = Integer.parseInt(bufferedReader.readLine());
        line = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < M; i++) {
            int insert = Integer.parseInt(line.nextToken());
            for (int j = 0; j < N; j++) {
                LinkedList<Integer> inObject = queuestack.get(j);
                inObject.add(insert);
                if (isStack[j] == 0) { // queue
                    insert = inObject.pollFirst();
                } else { // stack
                    insert = inObject.pollLast();
                }
                queuestack.remove(j);
                queuestack.add(j, inObject);
            }

            bufferedWriter.write(insert + " ");
        }
        bufferedWriter.flush();
        bufferedWriter.close();
    }
}

이후에도 자료구조만 조금씩 수정해서 몇 번 비슷하게 제출했다.

 

+ 여담..

처음에는 O(N + M * N)이라고 생각했는데 아니었다.

ArrayList는 내부가 배열로 이루어져있다.

 

ArrayList

그래서 값을 삭제하려면 새 배열을 만들고 삭제하려는 값만 빼고 새 배열에 복사해 넣기 때문에 O(N)이 걸리고,

 

O(N)

값을 추가하려면 또 새 배열을 만들고 배열을 복사, 새 값 추가를 해서 O(N)이 걸린다.

 

O(N)

 

내 눈에만 안보일 뿐이지 계속 O(N)씩 소요된다..

---

 

초반에는 첫번째 반복문에서 입력받은 수를 ArrayList에 넣어주고, 두번째 반복문에서는 ArrayList를 순서대로 탐색하며 내부에 들은 수를 바꿔주는 방법으로 진행했는데 계속해서 시간초과가 계속 떠서 이후에는 방법을 조금 바꿔보았다.

 

예제의 설명을 보다가 알게된건데 queuestack 내부의 자료구조가 queue라면 넣었던 값이 남아있고 기존 값이 밖으로 나온다.

그리고 stack이라면 마지막에 넣은게 나오기 때문에 넣었던 값이 그대로 나와서 다음으로 넘어간다.

 

그래서.. stack일때는 queuestack에 값을 아예 안넣었다.

 

그 후 남은 값들을 보면 새로 넣으려는 값이 queuestack의 제일 앞에 남고, queuestack의 마지막 값이 출력되는 것을 볼 수 있다.

 

중간에 또 시간초과가 뜨긴 했지만 위의 방식으로 시간초과 없도록 코드를 수정했다.

 

풀이 방법을 찾고나서 queuestack을 int 배열로 하려했는데, queuestack에서 queue가 몇개나 나올지 몰라서 추가가 자유로운 ArrayList로 했다.

 

여기서 또 시간초과가 뜨는데..

이유는 첫번째 제출했을때의 문제와 같다.

 

위의 풀이방법대로 하면 ArrayList의 제일 앞에 새로 넣는 값을 삽입하고, 기존 값들은 뒤로 한칸씩 밀려난다.

그러면 O(N + M * 2N)..

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(bufferedReader.readLine());
        ArrayList<Integer> queuestack = new ArrayList<>();

        StringTokenizer isQueueOrStack = new StringTokenizer(bufferedReader.readLine());
        StringTokenizer line = new StringTokenizer(bufferedReader.readLine());

        for (int i = 0; i < N; i++) {
            int insert = Integer.parseInt(line.nextToken());
            // stack일때는 넣으려는 수 그대로 가기 때문에 확인 안함
            if (Integer.parseInt(isQueueOrStack.nextToken()) == 0) {
                queuestack.add(insert);
            }
        }

        int M = Integer.parseInt(bufferedReader.readLine());
        line = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < M; i++) {
 	        // 처음 넣는 값은 제일 앞으로 들어가고, 마지막 queue의 값이 나오게되어있음
            int insert = Integer.parseInt(line.nextToken());
            queuestack.add(0, insert);
            bufferedWriter.write(queuestack.remove(queuestack.size() - 1) + " ");
        }
        bufferedWriter.flush();
        bufferedWriter.close();
    }
}

---

 

LinkedList는 내부가 Node로 이루어져있고 제일 앞에 값을 추가하려면 Node를 하나 만들고 앞에 연결만 해주면 되기때문에 시간복잡도가 O(1)이다.

 

그러면 시간복잡도가 O(N + M)으로 문제를 풀 수 있다.

그렇게해서 최종으로 나온 코드는 아래와 같다.

🙋‍♀️ 성공

import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(bufferedReader.readLine());
        LinkedList<Integer> queuestack = new LinkedList<>();

        StringTokenizer isQueueOrStack = new StringTokenizer(bufferedReader.readLine());
        StringTokenizer line = new StringTokenizer(bufferedReader.readLine());

        for (int i = 0; i < N; i++) {
            int insert = Integer.parseInt(line.nextToken());
            // stack일때는 넣으려는 수 그대로 가기 때문에 확인 안함
            if (Integer.parseInt(isQueueOrStack.nextToken()) == 0) {
                queuestack.add(insert);
            }
        }

        int M = Integer.parseInt(bufferedReader.readLine());
        line = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < M; i++) {
        	// 처음 넣는 값은 제일 앞으로 들어가고, 마지막 queue의 값이 나오게되어있음
            int insert = Integer.parseInt(line.nextToken());
            queuestack.addFirst(insert);
            bufferedWriter.write(queuestack.pollLast() + " ");
        }
        bufferedWriter.flush();
        bufferedWriter.close();
    }
}

(ง  •̀_•́ )ง