[백준_JAVA_알고리즘] 24511 queuestack

 

시간초과 코드

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

public class Main {

    static LinkedList<Integer> queuestack = new LinkedList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;
        StringBuilder stringBuilder = new StringBuilder();
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
        int temp = 0;

        // 첫째 줄: 자료구조의 개수 N
        int N = Integer.parseInt(bufferedReader.readLine());

        //둘째 줄: 0이면 큐, 1이면 스택
        int[] arrA = new int[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0; i < N; i++) {
            temp = Integer.parseInt(stringTokenizer.nextToken());
            arrA[i] = temp;
        }

        // 셋째 줄: 수열 B는 i번째 자료구조에 들어있는 원소
        int[] arrB = new int[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for(int i = 0; i < N; i++){
            temp = Integer.parseInt(stringTokenizer.nextToken());
            arrB[i] = temp;

            if(arrA[i] == 0){
                queuestack.push(temp);
            }
        }

        // 넷째 줄: 수열의 길이 M 주어짐
        int M = Integer.parseInt(bufferedReader.readLine());

        //다섯째 줄: 길이 M의 수열 C
        int[] arrC = new int[M];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for(int i = 0; i < M; i++){
            temp = Integer.parseInt(stringTokenizer.nextToken());
            arrC[i] = temp;

            if(arrA[i] == 0){
                queuestack.add(temp);
            }
        }
        for(int i = 0; i < M; i++){
            stringBuilder.append(queuestack.get(i)).append(" ");
        }
        bufferedWriter.write(String.valueOf(stringBuilder));
        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

 

정답  코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(bufferedReader.readLine());
        int[] arr = new int[N];
        Deque<Integer> deque = new ArrayDeque<>();

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            if (arr[i] == 0)
                deque.addLast(num);
        }

        int M = Integer.parseInt(bufferedReader.readLine());
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0; i < M; i++) {
            deque.addFirst(Integer.parseInt(stringTokenizer.nextToken()));
            bufferedWriter.write(deque.pollLast()+" ");
        }
        bufferedWriter.flush();
    }
}

 

 

시간 초과가 난 이유는 다음과 같다.

1.         for(int i = 0; i < M; i++){
            stringBuilder.append(queuestack.get(i)).append(" ");
        } 

get(i) 방식으로 값을 참조하는 방식은 시간복잡도가 O(n)으로 시간이 오래 걸린다.

 

2.      static LinkedList<Integer> queuestack = new LinkedList<>();

LinkedList를 사용하면 값을 push 또는 add할 때 넣는 순서가 달라질 수 있다.

 

3.         bufferedWriter.write(String.valueOf(stringBuilder));

stringBuilder에 값을 넣고 출력하는 방식은 비효율적이다. deque를 구현하면 poll을 통해 바로 값을 출력할 수 있다.