[백준] 1021번: 회전하는 큐

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

1021번: 회전하는 큐

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());	// 큐의 크기
		int M = Integer.parseInt(st.nextToken());	// 뽑아내려고 하는 수의 개수
		int[] arr = new int[M];	// 뽑아내려고 하는 수의 위치
		int min = 0;	// 2번, 3번 연산의 최솟값
		LinkedList<Integer> list = new LinkedList<Integer>();
		
		st = new StringTokenizer(bf.readLine());
		
		for(int i=0; i<M; i++) 
			arr[i] = Integer.parseInt(st.nextToken());
		
		for(int i=1; i<=N; i++)
			list.add(i);

		for(int i=0; i<arr.length; i++) {
			
			// 현재 리스트의 값이 바로 뽑아내려고 하는 값일때
			if(arr[i] == list.peek()) {
				list.remove();
				continue;
			}
			
			// 뽑아내려고 하는 수를 2번연산(왼쪽으로 이동)을 하는 것이 더 이득일때
			if(list.indexOf(arr[i]) <= list.size()/2 ) {
				
				// 왼쪽으로 한칸씩 밀기 - 현재값 제거하고 마지막에 넣기
				while(list.peek() != arr[i]) {
					int temp = list.remove();
					list.add(temp);
					min ++;
				}
			}
			
			// 뽑아내려고 하는 수를 3번연산(오른쪽으로 이동)을 하는 것이 더 이득일때
			else {
				
				// 오른쪽으로 한칸씩 밀기 - 가장 마지막값을 현재값으로 넣기
				while(list.peek() != arr[i]) {
					int temp = list.get(list.size()-1);
					list.add(0, temp);
					list.remove(list.size()-1);
					min ++;
				}
			}
			
			list.remove();	// 뽑아내려고 하는 수가 첫번째 위치로 오면 뽑아낸다.
		}
		
		System.out.println(min);
		bf.close();
	}

}

풀이

문제를 잘 이해해야 한다. 

큐의 크기가 N개이면, 1 ~ N까지의 값이 들어간다.

그 후 1~N까지의 수 중 뽑으려고 하는 개수(M)과 뽑으려고 하는 순서의 위치가 주어진다.

2번, 3번 연산이 최솟값이 되도록 뽑아야하는데 2번, 3번 연산의 조건은 다음과 같다.

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

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

 

즉 뽑으려고 하는 순서의 위치가 왼쪽으로 이동시키는 것이 최솟값인지, 오른쪽으로 이동시키는 것이 최솟값인지 비교해가며 최솟값이 나오도록 풀어야한다.

 

N = 10 일때, 

list = [1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10] 이 된다.

 

여기서 1 ~ 6는 2번연산(왼쪽으로 이동)을 수행하는 것이 최솟값이고,

6 ~ 10은 3번연산(오른쪽으로 이동)을 수행하는 것이 최솟값이다.

즉 뽑으려고 하는 위치의 인덱스값이 list 사이즈의 반보다 작거나 같을때 -> 왼쪽이동,

list 사이즈의 반보다 클때 -> 오른쪽으로 이동 하는것이 최솟값이 된다.

 

왼쪽으로 이동하는 연산은 현재값을 제거하고, 제거한 현재값을 list에 넣어주면 된다.

오른쪽으로 이동하는 연산은 리스트의 마지막값을 제거하고, 리스트의 가장 첫번째에 제거한 값을 넣어주면 된다.