[백준/BOJ] 10866번 : 덱 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

10866번: 덱

---

- 문제 -

 

난이도 실버 4 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

https://comain.tistory.com/271

[백준/BOJ] 10828번 : 스택 (JAVA / 자바)

https://comain.tistory.com/272

[백준/BOJ] 10845번 : 큐 (JAVA / 자바)

덱은 스택과 큐를 합쳐놓은것과 같다. 스택은 뒤로 넣고 뒤로 빼고, 큐는 뒤로 넣고 앞으로 뺀다.

덱은 뒤로 넣고 앞과 뒤로 다 뺼 수 있고, 앞으로 넣고 앞과 뒤로 다 뺄 수 있다.

위 문제들처럼 두가지 방법으로 풀어볼 것이다.

1. 덱 자체를 사용하는 방법.

2. 덱을 구현하는 방법.

 

주의 할 점은 인덱스를 정하는 방법이다. 앞과 뒤로 다 들어갈 수 있고, 뒤로 넣은 다음 저장된 값이 하나 밖에 없으면 앞으로 뺏을때 그 값이 출력되어야한다.

 

그렇기때문에 앞에 저장해나가는 것은 인덱스로 맨 뒤에서 앞으로 저장해 나갈 것이다. 뒤로 저장하는 것은 맨 앞에서 뒤로 저장해 나갈 것이다.

 

코드로 보면 어렵지 않게 이해 할  수 있을 것이다. 코드를 보자.

---

-풀이-

1. 덱 자체를 직접 사용

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

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());
		StringBuilder sb = new StringBuilder();
		Deque<Integer> deq = 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" :
				deq.addFirst(Integer.parseInt(st.nextToken()));
				break;
			case "push_back" :
				deq.addLast(Integer.parseInt(st.nextToken()));
				break;
			case "pop_front" :
				if(deq.isEmpty()) sb.append(-1).append("\n");
				else sb.append(deq.pollFirst()).append("\n");
				break;
			case "pop_back" :
				if(deq.isEmpty()) sb.append(-1).append("\n");
				else sb.append(deq.pollLast()).append("\n");
				break;
			case "size" :
				sb.append(deq.size()).append("\n");
				break;
			case "empty" :
				if(deq.isEmpty()) sb.append(1).append("\n");
				else sb.append(0).append("\n");
				break;
			case "front" :
				if(deq.isEmpty()) sb.append(-1).append("\n");
				else sb.append(deq.peekFirst()).append("\n");
				break;
			case "back" :
				if(deq.isEmpty()) sb.append(-1).append("\n");
				else sb.append(deq.peekLast()).append("\n");
				break;
			}
		}
		System.out.println(sb);
	}

}

 

2. 덱을 구현

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

public class Main {
	static int[] deq = new int[10001];
	static int first = 0;
	static int last = 0;
	static int size = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String S = st.nextToken();
			
			switch (S) {
			case "push_front" :
				push_front(Integer.parseInt(st.nextToken()));
				break;
			case "push_back" :
				push_back(Integer.parseInt(st.nextToken()));
				break;
			case "pop_front" :
				sb.append(pop_front()).append("\n");
				break;
			case "pop_back" :
				sb.append(pop_back()).append("\n");
				break;
			case "size" :
				sb.append(size()).append("\n");
				break;
			case "empty" :
				sb.append(empty()).append("\n");
				break;
			case "front" :
				sb.append(front()).append("\n");
				break;
			case "back" :
				sb.append(back()).append("\n");
				break;
			}
		}
		System.out.println(sb);
	}
	
	public static void push_front(int X) {
		deq[first] = X;
		//first는 0부터 10000 > 9999로 점점 내려 갈 것이다.
		//필자는 0부터 값을 넣었지만 10000부터 넣어도 된다.
		//first는 0부터 시작이기에 0 -1이면 음수이기에 배열의 크기인 10001을 더하고, 나눠주고 나머지를 저장해준다.
		//10001을 나눠주는 이유는 이러게 하므로 10000에서 0으로 다시 돌아가는 경우를 따로 조건을 주지 않아도 된다.
		//다른 메소드에도 다 비슷한게 연산 될 것인데, 이유는 여기에 적힌대로 생각하면 된다.
		first = ((first - 1) + 10001) % 10001;
		size++;
	}
	
	public static void push_back(int X) {
		last = (last + 1) % 10001;
		deq[last] = X;
		size++;
	}
	
	public static int pop_front() {
		if(size == 0) {
			return -1;
		}else {
			first = (first + 1) % 10001;
			int PF = deq[first];
			size--;
			return PF;
		}
	}
	
	public static int pop_back() {
		if(size == 0) {
			return -1;
		}else {
			int PB = deq[last];
			last = ((last - 1) + 10001) % 10001;
			size--;
			return PB;
		}
	}
	
	public static int size() {
		return size;
	}
	
	public static int empty() {
		if(size == 0) {
			return 1;
		}else {
			return 0;
		}
	}
	
	public static int front() {
		if(size == 0) {
			return -1;
		}else {
			int F = deq[(first + 1) % 10001];
			return F;
		}
	}
	
	public static int back() {
		if(size == 0) {
			return -1;
		}else {
			int B = deq[last];
			return B;
		}
	}

}

---

-결과-

1번 방법

2번 방법

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.