[백준] 18258 - 큐2

1. 문제

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

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

#입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 
둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 
문제에 나와있지 않은 명령이 주어지는 경우는 없다.

2. 내 풀이

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


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


        int count = Integer.parseInt(bf.readLine()); // 명령의 갯수
        List<Integer> queue = new ArrayList<>();

        for(int i=0;i<count;i++){
            String input = bf.readLine();
            String[] part = input.split(" ");

            String order = part[0];
            int value=0;
            if(part.length==2){
                value = Integer.parseInt(part[1]);
            }
            switch (order) {
                case "push":
                    queue.add(value);
                    break;
                case "pop":
                    if (queue.isEmpty()) {
                        bw.write(-1 + "\n");
                    } else {
                        int popnum = queue.get(0);
                        queue.remove(Integer.valueOf(popnum));
                        bw.write(popnum + "\n");
                    }
                    break;
                case "size":
                    bw.write(queue.size() + "\n");
                    break;
                case "empty":
                    int isEmpty = queue.isEmpty() ? 1 : 0;
                    bw.write(isEmpty + "\n");
                    break;
                case "front":
                    if (queue.isEmpty()) {
                        bw.write(-1 + "\n");
                    } else {
                        bw.write(queue.get(0) + "\n");
                    }
                    break;
                case "back":
                    if (queue.isEmpty()) {
                        bw.write(-1 + "\n");
                    } else {
                        bw.write(queue.get(queue.size() - 1) + "\n");
                    }
                    break;
                default:
                    break;
            }
        }
        bw.flush();
        bw.close();

    }

}

큐는 동적으로 크기가 변환되는 특징을 가지고 있기 때문에 java의 배열로는 구현이 힘들다고 생각했다.

따라서 ArrayList를 이용하여 동적 배열 및 switch를 통해 메소드 case에 따른 동작을 지정해주었다.

하지만, 위 코드는 시간초과가 났다.

내 코드의 문제점은 다음과 같았다.

1. ArrayList를 큐로 사용한 점

• ArrayList를 큐로 사용하면 queue.remove(0)같은 연산은 O(N) 만큼의 시간이 걸린다
• ArrayList 대신 LinkedList나 ArrayDequeue 사용
• 또한 큐 구현에는 Dequeue가 더 적합하다.

2. queue.remove(Integer.valueOf(popnum));

• pop 에서 작성한 코드인데 어차피 맨 앞의 인덱스 빼는건데 왜 굳이 이렇게 사용했는지 모르겠음

3. 최종 풀이

import java.io.*;
import java.util.Deque;
import java.util.ArrayDeque;

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

        int count = Integer.parseInt(bf.readLine());
        Deque<Integer> queue = new ArrayDeque<>();

        for (int i = 0; i < count; i++) {
            String input = bf.readLine();
            String[] part = input.split(" ");

            switch (part[0]) {
                case "push":
                    queue.addLast(Integer.parseInt(part[1]));  // O(1) 연산
                    break;
                case "pop":
                    bw.write(queue.isEmpty() ? "-1\n" : queue.pollFirst() + "\n");  // O(1) 연산
                    break;
                case "size":
                    bw.write(queue.size() + "\n");
                    break;
                case "empty":
                    bw.write(queue.isEmpty() ? "1\n" : "0\n");
                    break;
                case "front":
                    bw.write(queue.isEmpty() ? "-1\n" : queue.peekFirst() + "\n");
                    break;
                case "back":
                    bw.write(queue.isEmpty() ? "-1\n" : queue.peekLast() + "\n");
                    break;
            }
        }
        bw.flush();
        bw.close();
    }
}

• Dequeue<Integer> queue = new ArrayDequeue<>(); 를 통해 큐 구현
• 정수를 입력하는 push에만 part[1] (사용자입력란) 넣어줌
• Dequeue 내 메소드 ex)pollFirst , peekFirst , peekLast 사용