티스토리 뷰

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

 

10866번: 덱

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

www.acmicpc.net

큐, 덱 Java

덱 사용 이해 문제

 

접근방법

자바에서 ArrayDeque 사용하기

덱의 개념을 익히고 실습하는 문제. (입력 크기가 너무 작아서 비효율적인 구현으로도 통과가 되지만, 가급적이면 연산 당 시간 복잡도가 O(1)이도록 구현해 주세요.)

문제 설명에 이렇게 적혀있어서 덱 구현해서 풀어야 하나 했지만. 모든연산이 O(1)이긴 한걸요.

 

소스코드

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

public class Q10866 {
    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());
        ArrayDeque deque = new ArrayDeque();

        for(int i = 0 ; i < n ; i++){
            String[] s = br.readLine().split(" ");
            String instruction = s[0];
            int element = 0;
            if(s.length > 1){
                 element = Integer.parseInt(s[1]);
            }

            switch (instruction) {
                case "push_front" :
                    deque.addFirst(element);
                    break;

                case "push_back" :
                    deque.add(element);
                    break;

                case "pop_front" :
                    Object popf = deque.pollFirst();
                    if(popf == null){
                        bw.write("-1\n");
                    }else{
                        bw.write(popf.toString()+"\n");
                    }
                    break;

                case "pop_back" :
                    Object popb = deque.pollLast();
                    if(popb == null){
                        bw.write("-1\n");
                    }else{
                        bw.write(popb.toString()+"\n");
                    }
                    break;
                case "size" :
                    bw.write(deque.size()+"\n");
                    break;
                case "empty" :
                    if(deque.isEmpty()){
                        bw.write("1\n");
                    }else{
                        bw.write("0\n");
                    }
                    break;
                case "front" :
                    if(deque.peekFirst() == null){
                        bw.write("-1\n");
                    }else{
                        bw.write(deque.peekFirst().toString()+"\n");
                    }
                    break;

                case "back":
                    if(deque.peekLast() == null){
                        bw.write("-1\n");
                    }else{
                        bw.write(deque.peekLast().toString()+"\n");
                    }
            }

        }

        br.close();
        bw.close();
    }
}
댓글
댓글쓰기 폼