[알고리즘] Deque(덱 알고리즘)_JAVA[자바] 백준-28279번 풀이

 

 

덱 알고리즘을 이해하고 덱알고리즘을 사용한 문제를 풀어보자.

 

덱 알고리즘이란?

덱 알고리즘은 큐 알고리즘을 변형한 자료구조입니다. 큐알고리즘은 Front에서는 데이터를 꺼낼 수만 있고 Rear은 데이터를 삽입만 가능합니다. 하지만 덱은 Front와 Rear모두 데이터를 삽입, 추출이 가능한 알고리즘입니다.

 

다음은 데큐에서 Fornt와 Rear에서 인큐 데큐가 동작하는 예시입니다.

---

 

문제풀이

데큐또한 자바에서 지원하는 메서드가 존재합니다. 하지만 이번 풀이에서도 예시를 든 문제이기 때문에 직접 데큐 알고리즘을 작성해 해당 문제를 풀어보도록 하겠습니다.

문제에서 보면 총 8개의 데큐 메소드를 만들어야 하는 것을 볼 수 있습니다.

문제풀이방법

해당 문제도 간단하게 해결할 수 있습니다. 큐에서 사용한 놀리적인 위치인 Front와 Rear을 변수로 사용해 Front에 인큐를 할 때에는 Front을 감소시키고 반대로 Rear에 인큐할 때에는 Front을 증가시키면되며, Front에서 데큐할때에는 Front의 변수를 증가시키고, Rear에서 데큐 할때에는 Rear의 변수를 감소시키기만 하면 간단하게 구현할 수 있다.

 

public class 덱2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int a = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        Deck deck = new Deck(a);

        for (int i =0;i<a;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int token = Integer.parseInt(st.nextToken());
            switch (token){
                case 1:
                    int b = Integer.parseInt(st.nextToken());
                    deck.enqueFront(b);
                    break;
                case 2:
                    int c = Integer.parseInt(st.nextToken());
                    deck.enqueRear(c);
                    break;
                case 3:
                    int dequeFront = deck.dequeFront();
                    sb.append(dequeFront+"\n");
                    break;
                case 4:
                    int dequeRear = deck.dequeRear();
                    sb.append(dequeRear+"\n");
                    break;
                case 5:
                    int size = deck.size();
                    sb.append(size+"\n");
                    break;
                case 6:
                    int empty = deck.empty();
                    sb.append(empty+"\n");
                    break;
                case 7:
                    int peekFront = deck.peekFront();
                    sb.append(peekFront+"\n");
                    break;
                case 8:
                    int peekRear = deck.peekRear();
                    sb.append(peekRear+"\n");
                    break;
            }
        }
        System.out.println(sb);
        br.close();
    }

    public static class Deck{
        private int[] deck;
        private int front;
        private int rear;
        private int capacity;
        private int num;

        public Deck(int max){
            front = num=rear =0;
            capacity=max;
            deck= new int[capacity];
        }
        //덱의 맨앞에 데이터를 인큐
        public void enqueFront(int x){
            num++;
            if (--front<0)
                front=capacity-1;
            deck[front] =x;
        }
        //덱의 맨뒤 데이터를 인큐
        public void enqueRear(int x){
            deck[rear++]=x;
            num++;
            if (rear==capacity)
                rear=0;
        }
        //덱의 맨앞에서 데이터를 디큐
        public int dequeFront(){
            if (num<=0){
                return -1;
            }
            int x = deck[front++];
            if (front==capacity){
                front=0;
            }
            num--;
            return x;
        }
        //덱의 맨뒤에서 데이터를 디큐
        public int dequeRear(){
            if (num<=0){
                return -1;
            }
            if (--rear<0)
                rear=capacity-1;
            int x= deck[rear];
            num--;
            return x;
        }
        //--- 덱에 쌓여있는 데이터수를 반환합니다 ---//
        public int size(){
            return num;
        }
        //--- 덱이 비어 있는가? ---//
        public int empty(){
            if (num<=0)
                return 1;
            else
                return 0;
        }
        //--- 덱의 맨앞 데이터를 피크(맨앞 데이터를 들여다봄 ) ---*/
        public int peekFront(){
            if (num<=0){
                return -1;
            }
            return deck[front];

        }
        //--- 덱의 맨끝에서 데이터를 피크(맨끝 데이터를 들여다봄 ) ---*/
        public int peekRear(){
            if (num<=0){
                return -1;
            }

            return deck[rear==0 ? capacity-1 : rear-1]; 	//삼항연산자를 통해서 출력
        }
    }
}

정상적으로 문제를 맞는 거를 볼 수 있습니다.!