본문 바로가기
Programando/Algorithm

덱과 JAVA Deque 클래스

countrym 2021. 6. 18.

: 데이터를 앞, 뒤에서 삽입하거나 삭제할 수 있는 자료구조로, 스택과 큐의 성질이 적절하게 섞였다. 

 

클래스로 덱 구현하기

  • 덱 노드 클래스 : Node - 덱에 저장할 변수 num과 덱의 왼쪽 노드를 저장하는 left, 덱의 오른쪽 노드를 저장하는 right로 이루어져 있다.
  • 생성자 : Deque - front, rear를 null로 설정하고, count를 0으로 설정한다.
  • push 메서드
    • pushFront - 전달받은 데이터를 새로운 Node 객체에 넣고, 덱이 비어있는지 확인한다. 덱이 비어있다면 해당 Node를 front와 rear에 넣어주고, 노드의 left와 right를 null로 설정한다. 덱이 비어있지 않다면 현재 front의 left에 Node를 넣어주고, Node의 left는 null로 설정하고 right에 front를 넣은 다음에 front를 Node로 바꿔준다.
    • pushBack - 전달받은 데이터를 새로운 Node 객체에 넣고, 덱이 비어있는지 확인한다. 덱이 비어있다면 해당 Node를 front와 rear에 넣어주고, 노드의 left와 right를 null로 설정한다. 덱이 비어있지 않다면 현재 rear의 right에 Node를 넣어주고, Node의 right는 null로 설정하고 left에 rear를 넣은 다음에 rear를 Node로 바꿔준다.
  • pop 메서드
    • popFront - 덱이 비어있다면 -1을 반환하고, 비어있지 않다면 front의 값은 반환할 타입의 변수에 담는다. 그 후에 front의 right가 존재한다면 front의 right인 Node의 left를 null로 설정하고 front를 해당 Node로 바꿔준 다음에 값을 반환한다. front의 right가 존재하지 않으면 front와 rear를 null로 설정하고 값을 반환한다.
    • popBack - 덱이 비어있다면 -1을 반환하고, 비어있지 않다면 rear의 값은 반환할 타입의 변수에 담는다. 그 후에 rear의 left가 존재한다면 rear의 left인 Node의 right를 null로 설정하고 rear를 해당 Node로 바꿔준 다음에 값을 반환한다. rear의 left가 존재하지 않으면 front와 rear를 null로 설정하고 값을 반환한다.
  • size 메서드 : size - push 메서드가 불릴 때마다 count를 하나씩 더하고, pop 메서드가 불릴 때마다 count를 하나씩 빼서 저장한 count의 값을 반환한다.
  • empty 메서드 : empty - front가 null이라면 1을 반환하고, front가 null이 아니라면 0을 반환한다.
  • front 메서드 : empty 메서드의 값이 1이라면 -1을 반환하고, 아니라면 front의 num을 반환한다.
  • back 메서드 : empty 메서드의 값이 1이라면 -1을 반환하고, 아니라면 rear의 num을 반환한다.

 

 

덱 알고리즘 코드

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

 

10866번: 덱

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

www.acmicpc.net

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class Node {
    
    int num;
    Node left;
    Node right;
    
}

class Deque {
    
    Node front;
    Node rear;
    int count;
    
    public Deque() {
        
        front = null;
        rear = null;
        count = 0;
        
    }
    
    public int empty() {
        
        if(front == null) {
            return 1;
        } else {
            return 0;
        }
        
    }
    
    public void pushFront(int item) {
        
        Node node = new Node();
        node.num = item;
        count++;
        
        if(empty() == 1) {
            front = node;
            rear = node;
            node.left = null;
            node.right = null;
        }
        else {
            front.left = node;
            node.right = front;
            node.left = null;
            front = node;
        }
        
    }
    
    public void pushBack(int item) {
        
        Node node = new Node();
        node.num = item;
        count++;
        
        if(empty() == 1) {
            front = node;
            rear = node;
            node.left = null;
            node.right = null;
        }
        else {
            rear.right = node;
            node.left = rear;
            node.right = null;
            rear = node;
        }
    }
    
    public int popFront() {
        if(empty() == 1) {
            return -1;
        }
        else {
            int item = front.num;
            count--;
            if(front.right == null) {
                front = null;
                rear = null;
            }
            else {
                front = front.right;
                front.left = null;
            }
            return item;
        }
        
    }
    
    public int popBack() {
        if(empty() == 1) {
            return -1;
        }
        else {
            int item = rear.num;
            count--;
            if(rear.left == null) {
                front = null;
                rear = null;
            }
            else {
                rear = rear.left;
                rear.right = null;
            }
            return item;
        }
        
    }
    
    public int size() {
        return count;
    }
    
    public int front() {
        if(empty() == 1) {
            return -1;
        }
        return front.num;
    }
    
    public int back() {
        if(empty() == 1) {
            return -1;
        }
        return rear.num;
    }
    
}

public class Main
{
	public static void main(String[] args) throws IOException {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		Deque deque = new Deque();
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++)
		{
		    
		    String command = br.readLine();
		    if(command.contains("push_front"))
		    {
		        deque.pushFront(Integer.parseInt(command.split(" ")[1]));
		    }
		    else if(command.contains("push_back")) 
		    {
		        deque.pushBack(Integer.parseInt(command.split(" ")[1]));
		    }
		    else if(command.contains("pop_front"))
		    {
		        sb.append(deque.popFront()).append("\n");
		    }
		    else if(command.contains("pop_back"))
		    {
		        sb.append(deque.popBack()).append("\n");
		    }
		    else if(command.equals("size"))
		    {
		        sb.append(deque.size()).append("\n");
		    }
		    else if(command.equals("empty"))
		    {
		        sb.append(deque.empty()).append("\n");
		    }
		    else if(command.equals("front"))
		    {
		        sb.append(deque.front()).append("\n");
		    }
		    else if(command.equals("back")) {
		        sb.append(deque.back()).append("\n");
		    }
		    
		}
		
		System.out.println(sb);
	}
}

 

JAVA Deque 클래스

Deque 선언

import java.util.Deque;
import java.util.LinkedList;

Deque<DequeType> deque = new LinkedList<>();
// Deque를 LinkedList로 구현

 

Deque 메서드

push deque

Deque<Integer> deque = new LinkedList<>();

deque.addFirst(1); // 덱의 front에서 1을 삽입
// deque : 1, front = 1, rear = 1
deque.addFirst(2);
// deque : 2 1, front = 2, rear = 1
deque.addLast(3); // 덱의 rear에서 3을 삽입
// deque : 2 1 3, front = 2, rear = 3
deque.offerFirst(4); // 덱의 front에서 4를 삽입
// deque : 4 2 1 3, front = 4, rear = 3
deque.offerLast(5); // 덱의 rear에서 5를 삽입
// deque : 4 2 1 3 5, front = 4, rear = 5
deque.offerLast(6);
// deque : 4 2 1 3 5 6, front = 4, rear = 6
deque.addFirst(7);
// deque : 7 4 2 1 3 5 6, front = 7, rear = 6

: 덱이 꽉 차 있을 경우, offer__(value) 메소드는 false를 반환하고 add__(value) 메소드는 덱이 꽉차는 상황에서 예외를 발생시킨다.

 

pop deque

// deque : 7 4 2 1 3 5 6, front = 7, rear = 6

deque.pollFirst(); // 덱에서 front인 7을 삭제
// deque : 4 2 1 3 5 6, front = 4, rear = 6
deque.pollLast(); // 덱에서 rear인 6을 삭제
// deque : 4 2 1 3 5, front = 4, rear = 5
deque.removeFirst(); // 덱에서 front인 4를 삭제
// deque : 2 1 3 5, front = 2, rear = 5
deque.removeLast(); // 덱에서 rear인 5 삭제
// deque : 2 1 3, front = 2, rear = 3

: 덱이 비어있을 경우, poll__( ) 메소드는 null을 리턴하고 remove__( ) 메소드는 예외를 발생시킨다.

그 외

// deque : 2 1 3, front = 2, rear = 3

getFirst() // 덱의 가장 앞에 있는 값 2를 리턴
getLast() // 덱의 가장 끝에 있는 값 3을 리턴
peekFirst() // 덱의 가장 앞에 있는 값 2를 리턴
peekLast() // 덱의 가장 끝에 있는 값 3을 리턴
size() // 덱의 사이즈 3을 리턴

: peek__( ) 메소드는 덱이 비어있을 때 null을 리턴하고, get__( ) 메소드는 덱이 비어있을 때 예외를 발생시킨다.

JAVA Deque 클래스 사용 알고리즘 코드

출처 : https://www.acmicpc.net/problem/2346

 

2346번: 풍선 터뜨리기

첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자.

www.acmicpc.net

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Deque;
import java.util.ArrayDeque;

public class Main
{
	public static void main(String[] args) throws IOException {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		short N = Short.parseShort(br.readLine());
		
		Deque<int[]> deque = new ArrayDeque<>();
		
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(short i = 0; i < N; i++)
		{
		    deque.offerLast(new int[] {Integer.parseInt(st.nextToken()), i + 1});
		}
		
		int[] dq = new int[2];
		// dq[0] = 풍선에 적힌 숫자, dq[1] = 풍선의 번호
		
		int number = deque.peekFirst()[0];
		sb.append(deque.peekFirst()[1] + " ");
		deque.pollFirst();
		
		for(int i = 0; i < N; i++)
		{
			if(deque.isEmpty()) break;
		    
    		if(number > 0)
    		{
    			while(number > 1) {
        			deque.offerLast(deque.pollFirst());
        			number--;
    			}
    			number = deque.peekFirst()[0];
    			sb.append(deque.peekFirst()[1] + " ");
    			deque.pollFirst();
    		}
    		else
    		{
    			while(number < -1) {
    				deque.offerFirst(deque.pollLast());
    				number++;
    			}
    			number = deque.peekLast()[0];
    			sb.append(deque.peekLast()[1] + " ");
    			deque.pollLast();
    		}
		    
		}
		
		System.out.println(sb);
		
	}
}

 

 

덱 참고 사이트

반응형
저작자표시

'Programando > Algorithm' 카테고리의 다른 글

그래프의 탐색_BFS  (0) 2021.07.14
그래프(Graph)  (0) 2021.07.11
큐와 JAVA Queue 클래스  (0) 2021.06.15
스택과 JAVA Stack 클래스  (0) 2021.06.09
정렬: 좌표 압축  (0) 2021.05.29

'Programando/Algorithm' 관련글

티스토리툴바