18258 큐2 JAVA

이번 문제는 시간 복잡도가 O(1)이어야 한다.

O(1)이란 입력값의 크기에 상관없이 프로그램이 항상 일정한 시간에 실행되어야 한다는 조건이 있다.

이 조건을 알았다면, 문제를 다시 어떻게 해결해볼지 스스로 생각해보자.

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

 

이전에 큐 문제에선 약간 더럽게 작성했지만, 이번 문제를 해결하기 위해서 최대한 간략화하고, 메서드를 호출하는 것을 최소화하였다.

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

public class Q18258 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> deque = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        int T = Integer.valueOf(br.readLine());

        for (int i = 0; i < T; i++) {
            String input = br.readLine().trim();

            if(input.startsWith("push"))
                deque.offer(Integer.valueOf(input.substring(5)));
            else if(input.startsWith("pop"))
                sb.append(((deque.isEmpty()) ? -1 : deque.poll())).append("\n");
            else if(input.startsWith("size"))
                sb.append(deque.size()).append("\n");
            else if(input.startsWith("empty"))
                sb.append(deque.isEmpty() ? 1 : 0).append("\n");
            else if(input.startsWith("front"))
               sb.append((deque.isEmpty()) ? -1 : deque.peek()).append("\n");
            else if(input.startsWith("back"))
                sb.append((deque.isEmpty()) ? -1 : deque.peekLast()).append("\n");
        }

        System.out.println(sb);
    }
}

 

 

 

 

가능한 빠른 속도로 처리하기 위해 BufferedReader 클래스로 입력값을 읽어들였고, println메서드를 계속하여 호출하지 않고,

StringBuilder라는 mutable 클래스를 이용하여 작성하여 제출했더니, 문제가 되지 않았다. 여기서 더 최소화하자면 append("\n")을 굳이 한번 더 호출하지 않을 수 있겠지만, 알고만 넘어가겠다. 왜냐하면 append()는 O(1)의 시간 복잡도를 가지기 때문이다.

참고로 내 생각엔 String 클래스는 변경이 불가하기 때문에, 문자열을 결합할 때 마다 새로운 인스턴스를 생성하므로,시간 복잡도를 O(1)이라고 볼수 없고, 내 생각엔 String 클래스론 안되지 않을까 생각한다.