백준 1021: 회전하는 큐(java)

문제

---

풀이

 

덱을 사용하는 문제다. 목표하는 인덱스 앞 요소까지 반대편으로 옮겨 주고 pop()하여 푸는 문제이므로 다른 덱 문제들과 크게 다르지 않다.

2번 연산과 3번 연산 중 최소 반복 횟수를 구하기 위해서는 목표하는 요소의 위치가 덱의 절반 지점의 앞에 있는지 뒤에 있는지만 결정해주면 된다. 

int half;
if(deque.size()%2==0) 	//짝수 개
	half=deque.size()/2-1;
else
	half=deque.size()/2;

 

이때 덱의 크기가 짝수라면 size()에 2를 나눈 곳에서 1을 한번 더 빼 주어야 한다.

if(targetIndex<=half) {	//2번
	for(int j=0; j<targetIndex; j++) {
		deque.addLast(deque.pollFirst());
		count++;
	}
}
else {	//3번
	for(int j=0; j<deque.size()-targetIndex; j++) {
		deque.addFirst(deque.pollLast());
		count++;
	}
}
deque.pollFirst();

목표가 덱의 앞쪽에 있는 2번 연산의 경우 목표 인덱스 바로 앞 요소까지 반대편으로 보내주고, 이동시킨 횟수만큼 count를 증가시킨다. 3번 연산은 First와 Last를 반대로 하여 똑같이 수행하면 된다.

마지막으로 목표한 값에 도달하였을 때 poll()하여 목표 값을 제거한다.

 

전체 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		LinkedList<Integer> deque=new LinkedList<>();
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());

		for(int i=1; i<=N; i++){
			deque.add(i);
		}
		
		st=new StringTokenizer(br.readLine());
		int count=0;
		int[] targetArr=new int[M];
		
		for(int i=0; i<M; i++) {
			targetArr[i]=Integer.parseInt(st.nextToken());
			int targetIndex=deque.indexOf(targetArr[i]);
			
			int half;
			if(deque.size()%2==0) 	//짝수 개
				half=deque.size()/2-1;
			else
				half=deque.size()/2;
			
			if(targetIndex<=half) {	//2번
				for(int j=0; j<targetIndex; j++) {
					deque.addLast(deque.pollFirst());
					count++;
				}
			}
			else {	//3번
				for(int j=0; j<deque.size()-targetIndex; j++) {
					deque.addFirst(deque.pollLast());
					count++;
				}
			}
			deque.pollFirst();
		}
		System.out.println(count);
	}
}