[알고리즘/Java] 백준 1021번: 회전하는 큐

1. 문제

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

1021번: 회전하는 큐

---

2. 연관 알고리즘

• 자료 구조(Data Structures)
• 덱(Deque)

---

3. 풀이

❗ Deque(Double-Ended Queue)란, 데이터 삽입/제거 과정이 양방향 모두에서 가능하도록 구현된 큐(Queue)이다. 한편, 큐(Queue)는 일렬로 늘어선 줄이나 번호표가 주어진 은행 창구처럼 먼저 들어온 데이터가 먼저 나가는(FIFO, First In First Out) 형태로 저장하는 자료 구조 형식을 말한다. 여기서 가장 앞에 있는 데이터를 프론트(front), 가장 끝에 있는 데이터를 리어(rear)로 칭한다.

❗ ArrayDeque와 LinkedList는 Deque를 implements 하고 있는 Deque 인터페이스의 대표적 구현체이다.

ArrayDeque implements Deque / LinkedList implements Deque

• LinkedList는 데이터 접근성은 상대적으로 떨어지지만, 각 노드를 연결하고 있기에 추가/삭제/변경에 용이하고 배열(array)의 단점을 보완해 준다는 점에서 큐(Queue)를 구현할 때 유리하다고 '자바의 정석' 강의에서부터 익히 들어왔다: [자바의 정석] Ch 11. 컬렉션 프레임워크 강의 메모
• 문제에서 다룰 연산은 총 세 가지로 다음과 같다: ①첫 번째 원소 추출, ②왼쪽으로(끝으로) 한 칸 이동, ③오른쪽으로(앞으로) 한 칸 이동. 여기서 ②, ③번 연산을 위해서는 양방향의 삽입/제거가 가능한 덱(Deque)로의 구현이 필요한 셈이다.
• 그렇다면 덱(Deque)을 무엇으로 구현할지 고민이 됐는데, 풀이 과정 중 인덱스(index)를 활용해야 하므로  LinkedList를 선택하게 됐다.

int N = Integer.parseInt(st.nextToken()); //size of deque
int M = Integer.parseInt(st.nextToken()); //times to draw out

LinkedList<Integer> deque = new LinkedList<>();
for(int i=1; i <= N; i++) {
	deque.offer(i);
}

❗ 이때 add()는 추가할 대상 데이터가 없는 등 문제 상황에서 예외인 NullPointerException을 던지는 반면, offer()의 경우 추가 실패를 의미하는 false를 값으로서 반환해 동작 처리를 지속케 한다는 차이가 있다.

• 덱의 크기 N과 추출해야 할 횟수인 M이 주어진다. 구현체인 LinkedList로 덱을 정의하고, 1부터 N까지의 수로 초기화한다.

st = new StringTokenizer(br.readLine());
int count = 0;
while(M-- > 0) {
	int num = Integer.parseInt(st.nextToken());
	int idx = deque.indexOf(num); //java.util.LinkedList.indexOf()
	int mid = deque.size() / 2;
	//연산2. 왼쪽으로 한 칸 이동시킨다.
	if(idx <= mid) {
		while(num != deque.peek()) {
			deque.offerLast(deque.pollFirst());
			count++;
		}
	//연산3. 오른쪽으로 한 칸 이동시킨다.
	} else {
		while(num != deque.peek()) {
			deque.offerFirst(deque.pollLast());
			count++;
		}
	}
	//연산1. 첫 번째 원소를 뽑아낸다.
	deque.remove(); //equivalent to pollFirst()
}

• LinkedList의 메소드인 indexOf() 통해 주어진 숫자(num)가 가진 인덱스(idx)를 때마다 탐색해야 한다. 양방향으로 이동이 이뤄지고 있어 숫자별 위치가 계속 바뀌기 때문이다.
• deque.size() / 2 값인 mid를 정의해 탐색 인덱스(idx)가 중간 인덱스(mid) 이하인지 초과인지 구분해 연산을 치를 수 있도록 한다.
  • 즉 중간 인덱스(mid)보다 작거나 같다면 덱(deque)에서 앞부분에 위치해 있는 것이므로 해당 num이 peek()으로 조회될 때까지(해당 num이 가장 앞에 올 때까지) ②번 연산인 '왼쪽으로(끝으로) 한 칸 이동: offerLast(pollFirst())'을 반복하는 것이다.
  • 반대의 경우엔 덱(deque)에서 뒷부분에 위치해 있는 것이므로 해당 num이 peek()으로 조회될 때까지(해당 num이 가장 앞에 올 때까지) ③번 연산인 '오른쪽으로(앞으로) 한 칸 이동: offerFirst(pollLast())'를 반복한다.
  • peek()은 첫 번째 요소를 제거 없이 조회만 하는 메소드이다.
• 예를 들어 (N == 10 && M == 10)이고, 추출하고자 하는 수가 {1,6,3,2,7,9,8,4,10,5}인 경우 다음과 같은 연산이 일어난다. remove()는 pollFirst()와 같이 첫 번째 요소를 조회 및 제거하는 메소드이다.
  • {1} : (num == deque.peek())이므로
    • count +0(0)
    • remove() 1
  • {6} : (idx 4 <= mid)이므로
    • offerLast(pollFirst) 반복 - 2,3,4,5 끝으로 이동
    • count +4(4)
    • {6,7,8,9,10,2,3,4,5}
    • remove() 6
  • {3} : (idx 5 > mid)이므로
    • offerFirst(pollLast) 반복 - 5,4,3 앞으로 이동
    • count +3(7)
    • {3,4,5,7,8,9,10,2}
    • remove() 3
  • {2} : (idx 6 > mid)이므로
    • offerFirst(pollLast) 1회 - 2 앞으로 이동
    • count +1(8)
    • {2,4,5,7,8,9,10}
    • remove() 2
  • {7} : (idx 2 <= mid)이므로
    • offerLast(pollFirst) 반복 - 4,5 끝으로 이동
    • count +2(10)
    • {7,8,9,10,4,5}
    • remove() 7
  • {9} : (idx 1 <= mid)이므로
    • offerLast(pollFirst) 1회 - 8 끝으로 이동
    • count +1(11)
    • {9,10,4,5,8}
    • remove() 9
  • {8} : (idx 3 > mid)이므로
    • offerFirst(pollLast) 1회 - 8 앞으로 이동
    • count +1(12)
    • {8,10,4,5}
    • remove() 8
  • {4} : (idx 1 <= mid)이므로
    • offerLast(pollFirst) 1회 - 10 끝으로 이동
    • count +1(13)
    • {4,5,10}
    • remove() 4
  • {10} : (idx 1 <= mid)이므로
    • offerLast(pollLast) 1회 - 5 끝으로 이동
    • count +1(14)
    • {10,5}
    • remove() 10
  • {5} : (num == deque.peek())이므로
    • count +0(14)
    • remove() 5

---

4. 전체 코드

🌱GitHub(BOJ1021)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); //size of deque
		int M = Integer.parseInt(st.nextToken()); //times to draw out
		
		LinkedList<Integer> deque = new LinkedList<>();
		for(int i=1; i <= N; i++) {
			deque.offer(i);
		}
		
		st = new StringTokenizer(br.readLine());
		int count = 0;
		while(M-- > 0) {
			int num = Integer.parseInt(st.nextToken());
			int idx = deque.indexOf(num); //java.util.LinkedList.indexOf()
			int mid = deque.size() / 2;
			//연산2. 왼쪽으로 한 칸 이동시킨다.
			if(idx <= mid) {
				while(num != deque.peek()) {
					deque.offerLast(deque.pollFirst());
					count++;
				}
			//연산3. 오른쪽으로 한 칸 이동시킨다.
			} else {
				while(num != deque.peek()) {
					deque.offerFirst(deque.pollLast());
					count++;
				}
			}
			//연산1. 첫 번째 원소를 뽑아낸다.
			deque.remove(); //equivalent to pollFirst()
		}
		bw.append(count + "\n");
		bw.flush();
		bw.close();
		br.close();
	}
}