백준 1021 회전하는 큐 (Java)

1. 문제 링크

1021번: 회전하는 큐

 

2. 문제 및 입출력예제

 

3. 문제 풀이

문제가 큐라서 큐로 풀어보려고 했는데 위치를 찾기 위해 LinkedList로 풀었다.

LinkedList를 이용하니까 offer와 poll 모두 first와 last를 이용해 앞 뒤를 간단하게 확인할 수 있다.

찾아야 하는 원소의 위치를 찾고 중간보다 앞이라면 왼쪽으로, 중간보다 뒤라면 오른쪽으로 이동한다.

 

4. 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] split = br.readLine().split(" ");
		int N = Integer.parseInt(split[0]);
		int M = Integer.parseInt(split[1]);
		LinkedList<Integer> queue = new LinkedList<>();
		for(int i=1;i<N+1;i++) {
			queue.offer(i);
		}
		int[] num = new int[M];
		split = br.readLine().split(" ");
		for(int i=0;i<M;i++) {
			num[i] = Integer.parseInt(split[i]);
		}
		
		int size = 0, temp = 0, count = 0;
		for(int i=0;i<M;i++) {
			size = queue.size();
			if(size%2 == 0) {
				size = size/2-1;
			}
			else {
				size = size/2;
			}
			
			int where = queue.indexOf(num[i]); //찾을 원소의 위치 찾기
			if(where<=size) { //중간보다 앞이면 왼쪽 이동이 효율적
				for(int j=0;j<where;j++) {
					temp = queue.pollFirst();
					queue.offerLast(temp);
					count++;
				}
			}
			else { //오른쪽 이동이 효율적
				for(int j=where;j<queue.size();j++) {
					temp = queue.pollLast();
					queue.offerFirst(temp);
					count++;
				}
			}
			queue.pollFirst();
			
		}
		
		System.out.println(count);
	}
}