162. 1021(회전하는 큐) - 자바

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp1 = br.readLine().split(" ");

		int N = Integer.parseInt(tmp1[0]);
		int M = Integer.parseInt(tmp1[1]);

		//indexof 사용을 위해 deque대신 linkedlist 사용
		LinkedList<Integer> num = new LinkedList<>();
		Deque<Integer> innum = new ArrayDeque<>();
		int count = 0;

		String[] tmp2 = br.readLine().split(" ");
		ArrayList<Integer> tmpList = new ArrayList<>();
		
		for (int i = 0; i < tmp2.length; i++) {
			innum.add(Integer.parseInt(tmp2[i]));
		}

		for (int i = 1; i <= N; i++) {
			num.add(i);			
		}

		
		while (true) {
			if(num.peekFirst() == innum.peekFirst()) {
				num.pollFirst();
				innum.pollFirst();
				if(innum.size() == 0) break;
				else continue;				
			}
			
			if(num.size() / 2 >= num.indexOf(innum.peekFirst())){
				while(num.peekFirst() != innum.peekFirst()) {
					num.addLast(num.pollFirst());
					count++;
				}
			}
			
			else {
				while(num.peekFirst() != innum.peekFirst()) {
					num.addFirst(num.pollLast());
					count++;
				}
			}
		}
		
		System.out.println(count);

	}
}

문제요약

원소를 뽑는데 3가지 연산이 있는데 2,3번 연산을 최소로 사용한 횟수를 구하라.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

설명

문제를 자세히 보면 수를 뽑는 건 앞에서만 이루어진다.

다시 말해서 1번만 수를 뽑을 수 있다.

 

이를 예시로 들었을 때

다음과 같이 2를 먼저 뽑는데 2는 조건 2번을 이용하는게 가장 빠르다 따라서 2번을 1번 사용하여 수를 뽑는다.

그다음 9는 3번을 이용해서 뽑는게 가장 최소로 이용하는 방법이다.

따라서 3번을 3번 사용하여 수를 뽑는다.

마지막으로 5는 3번을 4번 이용하면 가장 최소로 이용할 수 있다.

 

결과적으로 1 + 3 + 4 로 총 8번으로 원하는 수를 뽑을 수 있다.

 

		//indexof 사용을 위해 deque대신 linkedlist 사용
		LinkedList<Integer> num = new LinkedList<>();
		Deque<Integer> innum = new ArrayDeque<>();
		int count = 0;

		String[] tmp2 = br.readLine().split(" ");
		ArrayList<Integer> tmpList = new ArrayList<>();
		
		for (int i = 0; i < tmp2.length; i++) {
			innum.add(Integer.parseInt(tmp2[i]));
		}

		for (int i = 1; i <= N; i++) {
			num.add(i);			
		}

왜 데큐대신 링크드 리스트를 썼지라고 생각할 수 있는데, 데큐에서는 indexOf 함수를 지원하지 않는다.

따라서 속도는 느리지만 문제를 풀기 위해 링크드리스트를 사용하였다.

 

 

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

			if(num.peekFirst() == innum.peekFirst()) {
				num.pollFirst();
				innum.pollFirst();
				if(innum.size() == 0) break;
				else continue;				
			}

만약 회전을 돌리는 데큐(num)의 맨 앞자리와 입력받은 뽑고자하는 수(innum)이 같다면 그 수를 뽑는다.

뽑고자하는 수가 남아있다면, 반복문을 계속 진행하고 그렇지 않다면 종료시킨다.

 

 

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

			if(num.size() / 2 >= num.indexOf(innum.peekFirst())){
				while(num.peekFirst() != innum.peekFirst()) {
					num.addLast(num.pollFirst());
					count++;
				}
			}

현재 길이의 반으로 나눈 값이 뽑고자 하는 수의 위치보다 크다면 (뽑고자 하는 수가 반보다 앞에있거나 같다)

2번 조건을 진행한다.

뽑을 수가 맨 앞으로 오기까지 cnt(count)를 증가 시킨다.

 

 

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

			else {
				while(num.peekFirst() != innum.peekFirst()) {
					num.addFirst(num.pollLast());
					count++;
				}
			}

2번 조건에 해당하지 않는다면 3번이 진행되며, 3번또한 뽑고자 하는 수가 맨앞에 오기까지 cnt를 증가시킨다.