[백준] 10866번 : 덱 - JAVA [자바]
10866번: 덱
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
-
문제
자료구조 덱을 이해하고 있는지를 확인하는 문제다.
기존의 덱 자료구조 원리를 이해하고 있다면 매우 쉽게 풀 수 있다.
- 알고리즘 [접근 방법]
이러한 문제는 자료구조 구현 문제로 이미 덱(Deque)에 대해 알고 있다면 크게 어렵지 않은 문제다.
일단, 덱(Deque)은 무엇인지 한 번 알아보자.
앞서 우리는 Queue(큐)를 다뤘었다. 큐는 '단방향'이면서 '선입선출(先入先出)' 즉, 먼저 들어간 데이터가 먼저 나오는 자료구조다. 단 방향이기 때문에 데이터를 넣는 입구와 데이터가 나오는 출구가 반대다. 쉽게 생각하면 에스컬레이터라고 보면 된다.
이렇게 단방향 자료구조이기 떄문에 역방향으로 참조하거나 반대로 넣어야 할 경우에는 큐 자료구조를 이용할 수가 없다. 이러한 한계점을 깨기 위해 입구와 출구를 양쪽에 모두 만든 자료구조가 바로 Deque(덱)이다.
Deque 의미 자체가 Double-ended Queue 의 줄임말이다.
큐와 덱의 구조 차이는 다음과 같다.
위에서 offer와 poll 은 Java API 기준으로 정해진 명칭이고, 문제에서 push와 pop의 경우 push = offer, pop = poll 이 된다. 또한 원소를 삭제하지 않고 얻기만 하려는 경우 문제에서는 front, back 이지만, Java 에서는 front = peekFirst, back = peekLast 에 해당된다는 점 미리 알고 가시길 바란다.
덱(Deque) 에 대한 자세한 구현 내용은 아래 글을 참고하시길 바란다. (사실 반드시 보고 오셨으면 한다)
자바 [JAVA] - 배열을 이용한 Deque (덱) 구현하기
•자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly..
st-lab.tistory.com
자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기
•자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly..
st-lab.tistory.com
그러면 어떻게 알고리즘을 풀이하느냐가 남아있다.
만약 자바에서 제공하는 컬렉션을 사용하고자 한다면 LinkedList 을 사용하는 방법과, ArrayDeque를 사용하는 방법이 있다. 두 클래스 모두 양방향으로 삽입 삭제가 가능하다.
또는 여러분들이 직접 int[] 배열을 두고 위 조건에 맞게 구현하는 것이다.
여러분이 직접 구현해야 할 경우 배열의 Index는 0부터 시작하기 때문에 만약 0부터 데이터를 채우려고 한다면 push_front가 들어올 경우 채우려는 인덱스가 자칫 음수값이 되어버리기 때문에 이 부분을 잘 처리해야 한다.
처리하는 방법은 크게 두 가지가 있는데,
1. 배열을 중간부터 시작한다.
2. front를 가리키는 값이 음수가 될 경우 배열의 가장 마지막 위치를 가리키게 하도록 한다.
1번 방식의 경우 입력받는 명령 수가 최대 10000개다. 이 때, push_front만 1만개가 들어올 수도 있고, push_back만 1만개가 들어 올 수 있기 때문에 20001 크기의 배열을 생성한 뒤 10000번째 인덱스부터 시작하는 것이다.
반대로 2번 방식의 경우 필자가 링크한 '배열을 이용한 덱 구현'에서 다뤘듯이 배열을 '원형'이라고 생각하고 만약 맨 앞의 원소의 인덱스가 0일 때 push_front를 한다면 배열의 가장 마지막 인덱스를 가리키도록 하는 것이다.
이에 대한 건 다음 링크를 클릭하시길 바란다.
자바 [JAVA] - 배열을 이용한 Deque (덱) 구현하기
•자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly..
st-lab.tistory.com
위 링크대로 할 경우 배열을 사용하는 공간은 10001개면 충분하다. (덱의 경우는 구현의 용이성을 위해 front위치의 공간은 비워둔다.
예로들어 전방에 삽입하고자 할 경우 다음과 같이 하면 된다.
이 때 주의해야 할 점은 '전방 삽입'의 경우 값을 추가하려는 인덱스가 0보다 작을 경우가 생길 수 있다.
예로들어 front = 0일 때 앞부분에 원소를 추가하면 front 값을 새로운 값으로 갱신시키게 된다. 이 때 front 에 1을 빼버리면 -1이 된다.
만약 front = (front - 1) % array.length 수식에 front = 0 이라면 어떻게 될까? 예로들어 용적(array.length)이 8이라고 해보자.
수식에 대입해보면 이럴 것이다.
(0 - 1) % 8
= -1 % 8
= ???
-1 을 8로 나눈 나머지 값은 얼마일까? 자바에서는 -1을 내보내게 된다. 하지만 배열에서 -1은 잘못된 접근인건 모두가 알 것이다.
이를 해결하기 위해서는 아주 간단하게 배열(용적)의 크기를 더해준 뒤 나머지 연산을 하면 된다.
쉽게 말해서 다음과 같이 하면 된다.
public void offerFirst(int item) {
array[front] = item; // front위치는 빈 공간이기 때문에 추가 해준 뒤 front 값을 갱신한다.
front = (front - 1 + array.length) % array.length;
size++; // 사이즈 1 증가
}
반대로 뒷 부분에 추가하는 것은 음수가 될 일이 없기 때문에 다음과 같이 하면 된다.
public void offerLast(int item) {
rear = (rear + 1) % array.length; // rear을 rear의 다음 위치로 갱신
array[rear] = item;
size++; // 사이즈 1 증가
}
간단하게 말해서 rear 또는 front가 오른쪽 방향으로 움직이는 경우는
rear = (rear + 1) % array.length; // rear을 rear의 다음 위치로 갱신
front = (front + 1) % array.length; // front을 front의 다음 위치로 갱신
왼쪽 방향으로 움직이는 경우는
rear = (rear - 1 + array.length) % array.length; // rear을 rear의 다음 위치로 갱신
front = (front - 1 + array.length) % array.length; // front을 front의 다음 위치로 갱신
이 두 공식을 알고 계시면 된다.
나머지 구체적인 구현은 코드를 보면서 이해해보도록 하자.
- 3가지 방법을 사용하여 풀이한다.
이 번에는 모두 BufferedReader을 입력 방식으로 통일하고, 구현 방식을 달리 해보려 한다.
앞서 말했던 자바 컬렉션을 이용하는 방법과 배열을 이용하되 중간 지점부터 시작할 것인지, front 또는 rear연산을 이용하여 원형 배열처럼 사용 하여 구현 할 것인지를 나누어 구현하겠다.
자바 컬렉션은 이 번에 Deque인 만큼 ArrayDeque 을 사용하겠다. 여러분들이 LinkedList를 쓰고 싶다면 ArrayDeque 대신 LinkedList로 바꿔주시면 된다.
또한 출력은 모두 StringBuilder 로 통일하겠다.
1. ArrayDeque
2. int[] 배열 방식 1
3. int[] 배열 방식 2
- 풀이
- 방법 1 : [ArrayDeque]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayDeque;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
String[] s = br.readLine().split(" ");
// 첫 번째 단어에 대한 switch-case
switch (s[0]) {
case "push_front": {
dq.addFirst(Integer.parseInt(s[1]));
break;
}
case "push_back": {
dq.addLast(Integer.parseInt(s[1]));
break;
}
case "pop_front": {
if (dq.isEmpty()) {
sb.append(-1).append('\n');
}
else {
sb.append(dq.pollFirst()).append('\n');
}
break;
}
case "pop_back": {
if (dq.isEmpty()) {
sb.append(-1).append('\n');
}
else {
sb.append(dq.pollLast()).append('\n');
}
break;
}
case "size": {
sb.append(dq.size()).append('\n');
break;
}
case "empty": {
if (dq.isEmpty()) {
sb.append(1).append('\n');
}
else {
sb.append(0).append('\n');
}
break;
}
case "front": {
if (dq.isEmpty()) {
sb.append(-1).append('\n');
}
else {
sb.append(dq.peekFirst()).append('\n');
}
break;
}
case "back": {
if (dq.isEmpty()) {
sb.append(-1).append('\n');
}
else {
sb.append(dq.peekLast()).append('\n');
}
break;
}
}
}
System.out.println(sb);
}
}
가장 기본적인 방법이라 할 수 있겠다.
이미 ArrayDeque에서 우리가 필요한 함수들이 모두 구현되어있기 때문에 각 case 별로 메소드와 출력문을 작성해주기만 하면 끝난다.
- 방법 2 : [int[] 배열 방식 1]
int 배열을 활용한 방식이다.
이 때 주의해아 할 점은 'front' 가 가리키는 인덱스는 비어있어야 한다. 이유는 아래 주석에서도 설명해놓았지만, 만약 아무 원소가 없는 상태에서 원소가 들어가면 front가 감소하거나, back이 증가할 것이다.
하지만 원소가 한 개 뿐일 경우에는 해당 원소는 front이자 back 원소이지만, 실제로는 front가 가리키는 위치에는 비어있게 된다.
이러한 예외를 처리하기 위해 만약 push_front 가 실행 될 경우 front을 먼저 감소시키는 것이 아닌 일단 front 위치에 원소를 넣은 뒤 front을 1 감소시켜야 한다.
그러면 어느 상황에서든 front 원소는 front + 1 에 위치하게 된다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static int front = 10000;
static int back = 10000;
static int size = 0;
static int[] deque = new int[20001];
/*
* Deque 배열에서 front가 최종적으로 가리키는 위치는 항상 비워둔다.
* 즉, 가장 앞에있는 원소는 front + 1이 된다.
*
* 이유는 만약 front의 최종 위치에 원소를 넣게 되면 다음과 같
* 예외가 발생한다.
*
* 예로들어 push_front(3) 을 실행하려 하는데 아무 원소도 없을 때
* front--; 감소시킨 뒤 deque[front] = 3; 이 되면
* deque[9999] = 3; 이 된다. 이때 front = 9999; back = 10000 이 된다.
*
* 하지만, 원소가 한 개만 있을 경우 해당 원소는 front 이자 back 원소가 된다.
* 이러한 경우를 방지하기 위해
* deque[front] 에 원소를 넣은 뒤, front--; 을 해준다.
*
* 결과적으로 front 요소 자체는 deque[front + 1] 위치에 자리한다.
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for(int i = 0; i < N; i++) {
String[] s = br.readLine().split(" ");
switch(s[0]) {
case "push_front" : {
push_front(Integer.parseInt(s[1]));
break;
}
case "push_back" : {
push_back(Integer.parseInt(s[1]));
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);
}
static void push_front(int val) {
// 원소를 먼저 넣은 뒤 front을 감소시킨다.
deque[front] = val;
front--;
size++;
}
static void push_back(int val) {
back++;
size++;
deque[back] = val;
}
static int pop_front() {
if (size == 0) {
return -1;
}
/*
* front + 1이 front 원소이므로 해당 원소를 임시 변수에 둔 뒤
* front 을 +1 증가시킨다.
*/
int ret = deque[front + 1];
front++;
size--;
return ret;
}
static int pop_back() {
if (size == 0) {
return -1;
}
int ret = deque[back];
back--;
size--;
return ret;
}
static int size() {
return size;
}
static int empty() {
if(size == 0) {
return 1;
}
return 0;
}
static int front() {
if(size == 0) {
return -1;
}
return deque[front + 1];
}
static int back() {
if(size == 0) {
return -1;
}
return deque[back];
}
}
크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.
- 방법 3 : [int[] 배열 방식 2]
int 배열을 활용한 방식 두 번째이다.
이 방법도 항상 최종적으로 front가 가리키는 인덱스는 항상 비어있다.
또한 원형 배열처럼 다루기 때문에 index를 조정 할 때 앞서 말했듯 나머지 연산을 이용하여야 한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static int front = 0;
static int back = 0;
static int size = 0;
static int[] deque = new int[10000];
/*
* Deque 배열에서 front가 최종적으로 가리키는 위치는 항상 비워둔다.
* 즉, 가장 앞에있는 원소는 front + 1이 된다.
*
* 이유는 만약 front의 최종 위치에 원소를 넣게 되면 다음과 같
* 예외가 발생한다.
*
* 예로들어 push_front(3) 을 실행하려 하는데 아무 원소도 없을 때
* front--; 감소시킨 뒤 deque[front] = 3; 이 되면
* deque[9999] = 3; 이 된다. 이때 front = 9999; back = 0 이 된다.
*
* 하지만, 원소가 한 개만 있을 경우 해당 원소는 front 이자 back 원소가 된다.
* 이러한 경우를 방지하기 위해 deque[front] 에 원소를 넣은 뒤,
* front = (front - 1 + array.length) % array.length; 을 해준다.
*
* 결과적으로 front 요소 자체는 deque[(front + 1) % array.length] 위치에 자리한다.
* ((front + 1) % array.length == (front + 1) % 10000)
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for(int i = 0; i < N; i++) {
String[] s = br.readLine().split(" ");
switch(s[0]) {
case "push_front" : {
push_front(Integer.parseInt(s[1]));
break;
}
case "push_back" : {
push_back(Integer.parseInt(s[1]));
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);
}
static void push_front(int val) {
// 원소를 먼저 넣은 뒤 front을 감소시킨다.
deque[front] = val;
// 음수가 되지 않도록 배열 크기만큼 더해준다.
front = (front - 1 + 10000) % 10000;
size++;
}
static void push_back(int val) {
/*
* deque[9999] 까지 꽉 찼을 경우 0으로 가리키기 위해
* 배열 크기만큼 나눠 나머지를 구한다.
*/
back = (back + 1) % 10000;
size++;
deque[back] = val;
}
static int pop_front() {
if (size == 0) {
return -1;
}
/*
* front + 1이 front 원소이므로 해당 원소를 임시 변수에 둔 뒤
* front 을 +1 증가시킨다.
*/
int ret = deque[(front + 1) % 10000];
front = (front + 1) % 10000;
size--;
return ret;
}
static int pop_back() {
if (size == 0) {
return -1;
}
int ret = deque[back];
back = (back - 1 + 10000) % 10000;
size--;
return ret;
}
static int size() {
return size;
}
static int empty() {
if(size == 0) {
return 1;
}
return 0;
}
static int front() {
if(size == 0) {
return -1;
}
return deque[(front + 1) % 10000];
}
static int back() {
if(size == 0) {
return -1;
}
return deque[back];
}
}
- 성능
채점 번호 : 26543923 - 방법 3 : int[] 배열 방식 2
채점 번호 : 26543923 - 방법 2 : int[] 배열 방식 1
채점 번호 : 26543923 - 방법 1 : ArrayDeque
알고리즘상으로 유의미한 차이는 크게 없다. (사실 ArrayDeque 또한 필자가 구현한 방식과 유사한 방식이라 그럴 것이다.)
- 정리
이 번 문제는 전형적인 자료구조 구현 문제라 만약 덱(Deque)을 한 번쯤 구현해봤다면 크게 어렵지 않게 구현했을 것이다.
다만 주의 할 점은 front와 back 변수가 어느 상황에 어떻게 가리키게 되는지를 잘 판단해야 한다.
'JAVA - 백준 [BAEK JOON] > 큐, 덱' 카테고리의 다른 글
| [백준] 5430번 : AC - JAVA [자바] (20) | 2021.03.07 |
|---|---|
| [백준] 1021번 : 회전하는 큐 - JAVA [자바] (0) | 2021.02.27 |
| [백준] 1966번 : 프린터 큐 - JAVA [자바] (10) | 2021.02.03 |
| [백준] 11866번 : 요세푸스 문제 0 - JAVA [자바] (10) | 2021.01.23 |
| [백준] 2164번 : 카드2 - JAVA [자바] (4) | 2020.12.19 |