[백준알고리즘-JAVA]1021번 풀이(회전하는 큐) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1021번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 1021 (회전하는 큐)

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

 

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

 

첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1,..., ak이었던 것이 a2,..., ak와 같이 된다.

왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1,..., ak가 a2,..., ak, a1이 된다.

오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1,..., ak가 ak, a1,..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

입력 예제, 출력 예제

성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static StringBuilder sb = new StringBuilder();
	static int count = 0;
	static LinkedList<Integer> q = new LinkedList<>();
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		
		int[] temp = new int[M];
		for(int i = 0 ; i < M ; i++)
			temp[i] = Integer.parseInt(st.nextToken());
		
		// 필요한 변수
		// 일단 뽑아낼 원소의 위치가 left가 빠른지 right가 빠른지 판별하는 것
		// 아마도 q.size 절반보다 작으면 left 아니면 right가 빠르다.
		// 그걸로 보내주면 끝
		for(int i = 1 ; i <= N ; i++)
			q.add(i);
		
		for(int i = 0 ; i < M ; i++) {
			
			if(check(temp[i])) {
				while(temp[i]!=q.get(0)) {
				q.addLast(q.pollFirst());
				count++;
				}
			}else {
				while(temp[i]!=q.get(0)) {
				q.addFirst(q.pollLast());
				count++;
				}
			}
			
			q.poll();
		}

		
		System.out.println(count);

		}
	public static boolean check(int a) {
		
		for(int i = 0 ; i <= q.size()/2 ; i++) {
			if(a == q.get(i))
				return true;
		}
		
		return false;
	}

}

회전하는 큐는 QUEUE 외에 DEQUEU의 개념을 이해한다면 아주 쉽게 풀리는 문제입니다. 그러면 STEP을 따라가 보면서 DEQUE와 알고리즘 풀이를 이해해 보도록 하죠

---

알고리즘 흐름도

입력받기 -> 뽑아낼 값 위치 찾아내기 -> 왼쪽, 오른쪽에서 뽑아낼지 정하기 -> 큐 회전하기 -> 출력하기

---

STEP1 Deque 이해하기

 

사실 이해할 것도 없습니다 Deque란 큐와 같은 형태이지만 큐는 FIFO형태입니다. 그러나 데큐는 FIFO와 LIFO의 특성을 모두 가지고 있습니다.

 

 이해하기 쉽게 먼저 들어온 값을 먼저 뽑아낼 수 있고 나중에 들어온 값을 먼저 뽑아낼 수 있습니다. 즉, 양쪽에서 뽑아낼 수 있다는 의미가 되죠.

 

주요 메서드를 보면 이해가 빠르실 겁니다.

 

addFirst() : 덱 맨 앞쪽에 값을 삽입하는 메서드

addLast() : 덱 마지막 쪽에 값을 삽입하는 메서드

 

pollFirst() : 덱 맨 앞쪽의 값을 빼오는 메서드

pollLast() : 덱 마지막 쪽의 값을 빼오는 메서드

 

간단하죠?

---

STEP2 뽑아올 값 위치 찾아내기

 

 자 이제 바로 문제를 풀이해야 합니다. 문제에서 원하는 것은 바로 최솟값입니다. 가장 빠르게 입력값들을 뽑아내면 되는 것이죠. 큐의 값은 순서대로 있다고 하니 더욱더 간단해집니다. q의 크기의 반보다 왼쪽에 있으면 왼쪽 연산을 오른쪽에 있으면 오른쪽 연산을 사용하면 되죠. 만약 홀수개라면 가운데는 왼쪽 연산을 따라야 하죠.

 

예를 들어 크기가 9 라면

 

1 2 3 4 5 6 7 8 9의 값이 들어있죠

 

5의 값을 가장 빨리끄내느 방법은 앞에 있는 1 ~ 4를 뺴낸뒤 poll 하는 방법이죠. 만약 9부터 빼낸다면 한 번 더 연산을 해야 되기 때문입니다.

 

이에 따라서 q.size()/2 만큼 인덱스를 왼쪽 연산으로 이해하셔야 합니다.

 

아직 이해가 안 가신다면, STEP 3을 따라가 보면서 완벽 이해를 해보도록 하죠

---

STEP 3 왼쪽인지 오른쪽인지 판별 구현하기

	public static boolean check(int a) {
		
		for(int i = 0 ; i <= q.size()/2 ; i++) {
			if(a == q.get(i))
				return true;
		}
		
		return false;
	}

간단합니다 인자로 받은 a가 q크기의 반보다 작은 곳에서 존재한다면 true를 반환합니다. 즉 true가 반환된다면, 왼쪽 연산을 수행하면 된다는 의미이죠 만약 아니라면 false 오른쪽 연산을 수행하면 됩니다.

 

 지금 다시 한번 생각해 보면 굳이 check함수를 안 만들고 실수 타입으로 만들어 2를 나눈 반올림 값을 사용하면 더욱 간단하게 식 표현이 가능해 보이네요 ㅎㅎ 

---

STEP 4 연산 수행 구현하기

 이제 연산 수행은 아주 간단합니다.

for(int i = 0 ; i < M ; i++) {
			
			if(check(temp[i])) {
				while(temp[i]!=q.get(0)) {
				q.addLast(q.pollFirst());
				count++;
				}
			}else {
				while(temp[i]!=q.get(0)) {
				q.addFirst(q.pollLast());
				count++;
				}
			}
			
			q.poll();
		}

앞서 만든 check함수를 활용해서 저희가 꺼내올 값을 최소한으로 꺼내오려면 왼쪽인지 오른쪽인지 판단합니다. 만약 true라면 앞쪽에서 꺼내서 뒤쪽으로 넣어주는 연산 즉, 왼쪽 연산을 실행해 줍니다.

 

아니라면 그 반대로 뒤쪽에서 꺼내서 앞쪽으로 넣어줍니다. 물론 저희는 횟수를 판별함으로 count를 세줍니다. 해당 값을 찾았으면 poll 해줍니다. 이를 계속 반복 후 count를 출력해주면 끝~