[백준 10845]- 덱- JAVA [배열 구현]

안녕하세요 놀이방 사장입니다.

 

이번 포스팅은 백준 10866번

"덱" 문제입니다.

 

10866번: 덱

 

덱은 큐에서 조금 더 진화된 자료구조라고 생각하시면 됩니다.

 

원래 기존에 큐는 FIFO구조인데 덱은 양옆이 뚫린 자료구조라고 생각하시면 됩니다.

EX) 앞에서도 데이터 추가가 되고 뒤에서도 데이터가 추가가됩니다.

물론 앞에서 데이터빼기가능, 뒤에서 데이터뺴기 가능

 

위에 나오는 이미지대로 구현해주면 됩니다.

 

코드를 보면서 설명하겠습니다.

먼저 배열을 이용해서 덱을 구현하는 것입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;


/*덱 직접 구현*/
public class Main{
    static int[] deq = new int[20001];
    static int front = 10000;
    static int back = 10000;
    static int size = 0;

    public static void addFront(int x){
        deq[front] = x;
        front--;
        size++;
    }

    public static void addback(int x){
        back++;
        deq[back] = x;
        size++;
    }

    public static int popFront(){
        if(size == 0 ){
            return -1;
        }
        int value = deq[front+1];
        front++;
        size--;
        return value;
    }

    public static int popBack(){
        if(size == 0){
            return -1;
        }
        int value = deq[back];
        back--;
        size--;
        return value;
    }

    public static int valFront(){
        if(size == 0){
            return -1;
        }
        return deq[front+1];
    }

    public static int valBack(){
        if(size == 0){
            return -1;
        }
        return deq[back];
    }

    public static int getSize(){
        return size;
    }

    public static int getEmpty(){
        if(size == 0){
            return 1;
        }else{
            return 0;
        }
    }

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());

        for(int i = 0; i< n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String S = st.nextToken();
            switch(S){
                case "push_front" :
                    addFront(Integer.parseInt(st.nextToken()));
                    break;
                case "push_back" :
                    addback(Integer.parseInt(st.nextToken()));
                    break;
                case "pop_front" :
                    System.out.println(popFront());
                    break;
                case "pop_back" :
                    System.out.println(popBack());
                    break;
                case "front" :
                    System.out.println(valFront());
                    break;
                case "back" :
                    System.out.println(valBack());
                    break;
                case "size" :
                    System.out.println(getSize());
                    break;
                case "empty" :
                    System.out.println(getEmpty());
                    break;
            }
        }
    }
}

위에 보면 배열을 20001크기를 설정한 이유는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다 이 부분 때문입니다.

아까 설명했듯이 덱은 앞,뒤 둘 다 데이터입출력이 가능해야하기 때문에 앞의 index 뒤에 index 둘 다 10000에서 시작합니다.

 

큐를 구현해보신 분들은 간단하게 이해가 되실거에요

addFront 앞에 데이터를 추가해줍니다.

앞 index가 들어왔으니 index -- 해서 앞으로 이동해줍니다.

 

addback 배열에 맨끝에 추가

데이터가 들어왔으니 index ++

 

popFront 맨 앞 데이터를 출력하고 삭제합니다.

먼저 -1예외처리해주고 value출력하고 인덱스 ++ 해서 덱 크기 줄이면 됩니다.

 

popBack 데이터 맨 뒤 데이터 출력하고 삭제합니다.

popFront반대로 해주면 됩니다.

 

valFront, valBack은 앞 데이터 출력, 뒤 데이터 출력휠씬 쉽죠 그냥 출력해주면됩니다.

 

getSize는 size라는 변수로 사이즈를 계속 관리했기 떄문에 그대로 출력getEmpty도 size변수를 이용해서 출력해주면 끝납니다.

 

두번째로는 자바에서 이미 구현된 덱을 사용하는 것입니다.

import java.util.ArrayDeque;

코드를 보시겠습니다.

 

/*자바 자료구조 이용*/
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.StringTokenizer;

public class Main{
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        ArrayDeque<Integer> dque = new ArrayDeque<Integer>();

        for(int i = 0; i< n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String S = st.nextToken();

            switch(S){
                case "push_front" :
                    dque.addFirst(Integer.parseInt(st.nextToken()));
                    break;
                case "push_back" :
                    dque.addLast(Integer.parseInt(st.nextToken()));
                    break;
                case "pop_front" :
                    if(dque.isEmpty()){
                        System.out.println("-1");
                    }else{
                        System.out.println(dque.pollFirst());
                    }
                    break;
                case "pop_back" :
                    if(dque.isEmpty()){
                        System.out.println("-1");
                    }else{
                        System.out.println(dque.pollLast());
                    }
                    break;
                case "size" :
                    System.out.println(dque.size());
                    break;
                case "empty" :
                    if(dque.isEmpty()){
                        System.out.println("1");
                    }else{
                        System.out.println("0");
                    }
                    break;
                case "front" :
                    if(dque.isEmpty()){
                        System.out.println("-1");
                    }else{
                        System.out.println(dque.peekFirst());
                    }
                    break;
                case "back" :
                    if(dque.isEmpty()){
                        System.out.println("-1");
                    }else{
                        System.out.println(dque.peekLast());
                    }
                    break;
            }
        }
    }
}

케이스문을 이용해서 각각 해당하는 메소드를 분기시켜주었습니다.

 

밑에 방법을 사용하면 아주 간단하지만 한 번쯤에 직접 구현하는 것도 좋은 습관인 것 같습니다

 

감사합니다.