[백준] 큐2 - 18258

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

 

해당 문제는 Queue로 풀 생각을 많이 하겠지만 front와 back 명령어를 쉽게 구현하기 위해 Deque을 사용하였다.

---

초기 코드

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

class Main {
    private static Deque<String> dq = new ArrayDeque<>();
    private static String cmd;
    private static String value;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        for (int n = 0; n < N; n++) {
            cmd = br.readLine();

            if (checkBlank(cmd)) {
                String[] separateCmd = cmd.split(" ");
                cmd = separateCmd[0];
                value = separateCmd[1];
            }

            applyCmdInQueue();
        }
    }

    private static boolean checkBlank(String cmd) {
        return cmd.contains(" ");
    }

    private static void applyCmdInQueue() {
        switch (cmd) {
            case "push":
                push();
                break;

            case "pop":
                pop();
                break;

            case "size":
                size();
                break;

            case "empty":
                empty();
                break;

            case "front":
                front();
                break;

            case "back":
                back();
                break;
        }
    }

    private static void push() {
        dq.add(value);
    }

    private static void pop() {
        String result = "-1";
        if (!dq.isEmpty()) {
            result = dq.removeFirst();
        }
        System.out.println(result);

    }

    private static void size() {
        System.out.println(dq.size());
    }

    private static void empty() {
        String result = "0";
        if (dq.isEmpty()) {
            result = "1";
        }
        System.out.println(result);
    }

    private static void front() {
        String result = "-1";
        if (!dq.isEmpty()) {
            result = dq.getFirst();
        }
        System.out.println(result);
    }

    private static void back() {
        String result = "-1";
        if (!dq.isEmpty()) {
            result = dq.getLast();
        }
        System.out.println(result);
    }
}

위의 코드는 시간초과가 발생한 코드이다. 해당 코드가 시간 초과가 발생한 이유는 N만큼 Switch-case 문을 반복하기 때문이라고 생각되지만 단순 계산했을 때 문제가 없다고 판단을 하긴했다. N의 최대값은 2,000,000 이고 명령어는 총 6개이기 때문에 최악의 상황으로 만약 모든 명령어가 back 명령어라면 2,000,000 * 6 = 12,000,000이기 때문에 충분히 1초안에 해결할 수 있다 생각하였다.

---

문제 해결

문제의 원인은 System.out.println()으로 값을 출력하는 것이 문제였다.

해당 문제는 최악의 경우 1200만번을 출력해야하는데,

System.out.println() 메서드를 여러 스레드가 사용하게 된다면 오버헤드가 발생하여 프로세스 처리가 늦어지게 될 수 있다.

 

따라서 해결 방안으로 BufferedWriter 입력 객체를 사용하였다.

 

 

BufferedWriter가 더 빠른 이유

BufferedWriter의 경우 데이터를 내부 버퍼에 저장하고 버퍼가 가득차면 한 번에 데이터를 출력하지만

sysout의 경우 호출될 때마다 즉시 출력하므로 반복적인 입출력 작업에서는 성능이 저하된다.

 

이러한 특성 때문에 I / O 작업의 횟수에서 성능차이가 발생하는 것이고 쉽게 말해 버퍼링 때문이라 할 수 있다.

이번 문제와 같이 출력 횟수가 1200만번이나 되는 경우에는 sysout 보다 bufferedWriter 방식이 더욱 빠르고 효율적이다.

---

최종 코드

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

class Main {
    private static Deque<String> dq = new ArrayDeque<>();
    private static String cmd;
    private static String value;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        for (int n = 0; n < N; n++) {
            cmd = br.readLine();

            if (checkBlank(cmd)) {
                String[] separateCmd = cmd.split(" ");
                cmd = separateCmd[0];
                value = separateCmd[1];
            }

            applyCmdInQueue(bw);
        }
        bw.flush();
        bw.close();
    }

    private static boolean checkBlank(String cmd) {
        return cmd.contains(" ");
    }

    private static void applyCmdInQueue(BufferedWriter bw) throws IOException {
        switch (cmd) {
            case "push":
                push();
                break;

            case "pop":
                bw.write(pop());
                bw.newLine();
                break;

            case "size":
                bw.write(size());
                bw.newLine();
                break;

            case "empty":
                bw.write(empty());
                bw.newLine();
                break;

            case "front":
                bw.write(front());
                bw.newLine();
                break;

            case "back":
                bw.write(back());
                bw.newLine();
                break;
        }
    }

    private static void push() {
        dq.add(value);
    }

    private static String pop() {
        String result = "-1";
        if (!dq.isEmpty()) {
            result = dq.removeFirst();
        }
        return result;
    }

    private static String size() {
        return String.valueOf(dq.size());
    }

    private static String empty() {
        String result = "0";
        if (dq.isEmpty()) {
            result = "1";
        }
        return result;
    }

    private static String front() {
        String result = "-1";
        if (!dq.isEmpty()) {
            result = dq.getFirst();
        }
        return result;
    }

    private static String back() {
        String result = "-1";
        if (!dq.isEmpty()) {
            result = dq.getLast();
        }
        return result;
    }
}