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

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

 

풀이 

앞, 뒤 양쪽으로 삽입/삭제가 가능한 자료구조인 Deque를 사용하면 좋겠다.

Deque인터페이스를 구현하는 ArrayDeque, LinkedList 클래스 중 선택한다.

 

1. 타겟이 맨 앞으로 올 때까지 이동시킨다.

 1.1 왼쪽으로 이동이 빠르다면

      첫 번째 요소를 마지막으로 옮긴다.

 1.2 오른쪽으로 이동이 빠르다면

      마지막 요소를 처음으로 옮긴다.

2. 타겟을 삭제한다.

3. 다음 타겟을 1번부터 반복한다.

 

공부할 내용

• StringTokenizer 기본 사용법
• Deque 기본 개념
• ArrayDeque vs LinkedList

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

public class Main1021 {

	public static void main(String[] args) throws IOException {
		LinkedList<Integer> deque = new LinkedList<Integer>();
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int count = 0;
		
		
		StringTokenizer tokenizer = new StringTokenizer(bf.readLine(), " ");
		int size = Integer.parseInt(tokenizer.nextToken());
		int theNumber = Integer.parseInt(tokenizer.nextToken());
		int[] arr = new int[theNumber];
		
		for(int i=0; i<size; i++) {
			deque.add(i+1);
		}//for end
		
		tokenizer = new StringTokenizer(bf.readLine(), " ");
		
		for(int i=0; i<theNumber; i++) {
			arr[i] = Integer.parseInt(tokenizer.nextToken());
		}//for end
		
		int currentIdx = 0;
		int target = 0;
		int currentDequeSize = 0;
		for(int i=0; i<theNumber; i++) {
			currentIdx = deque.indexOf(arr[i])+1;
			currentDequeSize = deque.size();
			if(currentIdx-1<=currentDequeSize-currentIdx+1) {
			//왼쪽 방향으로 이동 (2번 연산) - 맨 앞 요소를 맨 뒤로 이동
				while(currentIdx>1) {
					target = deque.removeFirst();
					deque.addLast(target);
					count++;
					currentIdx--;
				}//while end
				deque.removeFirst();
			} else {
			//오른쪽 방향으로 이동 (3번 연산) - 맨 뒷 요소를 맨 앞으로 이동
				while(currentIdx!=1) {
					target = deque.removeLast();
					deque.addFirst(target);
					count++;					
					currentIdx = (++currentIdx)%currentDequeSize;
				}//while end
				deque.removeFirst();
			}//if~ end
		}//for end
		
		System.out.println(count);
			
	}//main() end
	
}

 

** ArrayDeque vs LinkedList