BOJ - 덱

leehyunjon·2022년 11월 18일
Deque동적할당
0

Algorithm

목록 보기
128/162

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

Problem

Solve

덱을 이용하여 각 명령을 처리하는 문제입니다.
자바에서 제공하는 LinkedList나 ArrayDeque를 이용하여 풀수 있지만, 직접 구현해보겠습니다.
그리고 동적할당을 위해 resize도 추가해서 구현해볼 예정입니다.

먼저 나만의 덱 ArrayDeque를 생성해줍니다.

class ArrayDeque{
	int front;
    int rear;
    int size;
    int[] array;
    
    public ArrayDeque(int capacity){
    	front = 0;
        rear = 0;
        size = 0;
        array = new int[capacity];
    }
}

앞에 값을 추가한다면 front는 앞으로 이동하고, 뒤에 값을 추가한다면 rear를 뒤로 이동시켜줍니다.
front == rear라면 어떠한 값을 가지고 있지않는것이고, rear+1==front라면 해당 배열에 모든 값이 차있다는 뜻이됩니다.

그리고 front는 항상 빈 공간으로 남겨주어야합니다. 실질적인 값은 array[front+1]에 들어있게 됩니다. (그래야 front==end일때 빈값이라고 둘 수 있습니다.)

resize

값을 추가할때, 배열이 가득차있는 경우(front == rear+1) 기존 배열의 크기 2배로 새로운 배열을 생성하여줍니다.

그리고 i를 새로운 배열의 index, j를 기존 배열의 index로 선언하고 새로운 배열을 초기화하여 줍니다.

//i : 새로운 배열 index, j : 기존 배열의 index
for(int i=1, j=front+1;i<=size;i++, j++){
	newArray[i] = array[j%arrayCapacity];
}

그리고 난 후 front를 0, rear를 size로 갱신하여 새로운 배열로 덱을 사용하게 됩니다.

값을 추가할때뿐만 아니라, 값을 삭제했을 때도 현재 값이 들어있는 크기(size)가 현재 배열의 1/4의 크기보다 작다면 메모리 크기를 줄여줍니다.

private void resize(int newCapacity){
	int arrayCapacity = array.length;
	int[] newArray = new int[newCapacity];

	for(int i=1, j=front+1;i<=size;i++, j++){
		newArray[i] = array[j%arrayCapacity];
	}

	this.array = newArray;
	front = 0;
	rear = size;
}

push_front

		public void push_front(int x){
			if((rear+1)%array.length == front) resize(array.length*2);

			front = (front-1+array.length)%array.length;

			array[(front+1)%array.length] = x;
			size++;
		}
  • rear+1 == front라면 배열이 모든 가득차있는 경우이기 때문에 새로운 배열을 반환하여줍니다.
  • 앞에 값을 추가해주어야하기 때문에 front를 앞으로 한칸 이동시켜줍니다.
    • 앞으로 이동하였을때 front가 -1이 된다면 배열범위를 벗어나기 때문에 나누는 값을 더해주어 -1이 되었을때 배열의 맨 뒤쪽을 가리키도록 구현하여줍니다.
    • front = (front-1+array.length)%array.length
  • 현재 front에서 front+1에 추가되는 값을 저장하고 size를 증가시켜줍니다.

push_back

		public void push_back(int x){
			if((rear+1)%array.length == front) resize(array.length*2);

			rear = (rear+1)%array.length;

			array[rear] = x;
			size++;
		}
  • rear+1 == front일 경우 덱에 값이 가득차있는 경우이기 때문에 배열을 동적으로 할당하여줍니다.
  • 뒤에 값이 추가된다면 rear는 뒤로 한칸 이동하고 해당 rear에 추가되는 값을 갱신하여줍니다.
    • 뒤로 이동하였을때, 배열의 범위를 벗어날수 있기 때문에 배열의 크기를 나누어 나머지를 rear로 갱신하여줍니다.
    • rear = (rear+1)%array.length
  • size를 증가시켜줍니다.

pop_front

		public int pop_front(){
			if(front==rear) return -1;

			if(size-1 < array.length/4) resize(array.length/2);

			size--;
			front = (front+1)%array.length;

			return array[front];
		}
  • 맨 앞 값을 꺼내는 경우 front==rear인 경우 아무 값도 없는것이기 때문에 -1을 반환하여줍니다.
  • size를 줄였을때 기존 배열 크기의 1/4보다 작다면 배열을 재할당 해줍니다.
  • size를 줄여주고 front를 뒤로 한칸 이동시켜줍니다.
  • 현재 front의 값을 반환하여줍니다.

pop_back

		public int pop_back(){
			if(front==rear) return -1;

			if(size-1 < array.length/4) resize(array.length/2);

			size--;
			int result = array[rear];
			rear = ((rear-1)+array.length)%array.length;

			return result;
		}
  • 마찬가지로 front==rear인 경우 값이 없는 것이기 때문에 -1을 반환하여줍니다.
  • resize도 동일합니다.
  • rear같은 경우 rear에 마지막 값을 가리키고 있기 때문에 result에 현재 rear의 값을 저장하고 rear를 앞으로 한칸 이동시켜줍니다.
    • 앞으로 한칸 이동했을때, -1을 가져 범위 밖을 벗어날수 있습니다.
    • rear = (rear-1+array.length)%array.length
  • 저장한 result를 반환하여줍니다.

size

		public int size(){
			return size;
		}
  • 저장되어있는 현재 덱의 크기를 반환하여줍니다.

empty

		public int empty(){
			return rear-front == 0 ? 1 : 0;
		}
  • 삼항연산자를 이용하여 rear-front == 0 (= size == 0)인 경우 1을 반환하고 그렇지 않다면 0을 반환하여줍니다.

front

		public int front(){
			if(front==rear) return -1;
			return array[(front+1)%array.length];
		}
  • front==rear이라면 값을 가지고 있지 않기때문에 -1을 반환하여줍니다.
  • 그렇지 않다면 front+1의 값을 반환하여줍니다.
    • 이때도 front의 뒤에 위치한 값을 참조해야하기 때문에 배열의 크기를 나누어 나머지를 가리키도록 하여야합니다.

back

		public int back(){
			if(front==rear) return -1;
			return array[rear];
		}
  • fonrt==rear는 값이 없는 경우
  • rear는 마지막 값을 가리키고 있기 때문에 rear가 가리키는 값을 반환합니다.

Code

import java.io.*;
import java.util.StringTokenizer;
public class Main{
	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(10);
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<N;i++){
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			String method = st.nextToken();

			int x = 0;
			switch(method){
				case "push_front":
					x = Integer.parseInt(st.nextToken());
					deque.push_front(x);
					break;
				case "push_back":
					x = Integer.parseInt(st.nextToken());
					deque.push_back(x);
					break;
				case "pop_front":
					sb.append(deque.pop_front()).append("\n");
					break;
				case "pop_back":
					sb.append(deque.pop_back()).append("\n");
					break;
				case "size":
					sb.append(deque.size()).append("\n");
					break;
				case "empty":
					sb.append(deque.empty()).append("\n");
					break;
				case "front":
					sb.append(deque.front()).append("\n");
					break;
				case "back":
					sb.append(deque.back()).append("\n");
					break;
			}
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static class ArrayDeque{
		int front;
		int rear;
		int size;
		int[] array;
		public ArrayDeque(int capacity){
			front = 0;
			rear = 0;
			size = 0;
			array = new int[capacity];
		}

		public void push_front(int x){
			if((rear+1)%array.length == front) resize(array.length*2);

			front = (front-1+array.length)%array.length;

			array[(front+1)%array.length] = x;
			size++;
		}

		public void push_back(int x){
			if((rear+1)%array.length == front) resize(array.length*2);

			rear = (rear+1)%array.length;

			array[rear] = x;
			size++;
		}

		public int pop_front(){
			if(front==rear) return -1;

			if(size-1 < array.length/4) resize(array.length/2);

			size--;
			front = (front+1)%array.length;

			return array[front];
		}

		public int pop_back(){
			if(front==rear) return -1;

			if(size-1 < array.length/4) resize(array.length/2);

			size--;
			int result = array[rear];
			rear = ((rear-1)+array.length)%array.length;

			return result;
		}

		public int size(){
			return size;
		}

		public int empty(){
			return rear-front == 0 ? 1 : 0;
		}

		public int front(){
			if(front==rear) return -1;
			return array[(front+1)%array.length];
		}

		public int back(){
			if(front==rear) return -1;
			return array[rear];
		}

		private void resize(int newCapacity){
			int arrayCapacity = array.length;
			int[] newArray = new int[newCapacity];

			for(int i=1, j=front+1;i<=size;i++, j++){
				newArray[i] = array[j%arrayCapacity];
			}

			this.array = newArray;
			front = 0;
			rear = size;
		}
	}
}

Result

Reference

https://st-lab.tistory.com/185

profile
leehyunjon
내 꿈은 좋은 개발자
이전 포스트

BOJ - 네트워크 연결

다음 포스트

BOJ - 숨바꼭질 3

0개의 댓글