메모

/*
뽑고자하는 해당 원소가 전체 원소에서 중앙보다 앞에 있는지 뒤에 있는지에 따라 2번/3번 연산을 실행할 경우가 나뉘어짐
*/

---

해결법

방법 1

import java.util.Scanner;
import java.util.LinkedList;
 
public class Main {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);		// Scanner 객체 생성
		
		LinkedList<Integer> deque = new LinkedList<Integer>();		// LinkedList 선언
		
		int count = 0;			// 2, 3번 연산 횟수 누적 합 변수
		
		int N = in.nextInt();		// 큐의 크기(1 ~ N)
		int M = in.nextInt();		// 뽑으려는 숫자의 개수
		
		// 1 ~ N 까지 덱에 담아둔다.
		for (int i = 1; i <= N; i++) {
			deque.offer(i);
		}
		
        // 뽑고자 하는 수를 담은 배열 seq
		int[] seq = new int[M];		
		
		for (int i = 0; i < M; i++) {
			seq[i] = in.nextInt();
		}
		
        // 덱(배열 seq)에서 뽑고자 하는 숫자의 위치(index) 찾기 
		for (int i = 0; i < M; i++) {			
			int target_idx = deque.indexOf(seq[i]);		// 뽑고자 하는 원소(index)
			int half_idx;		// 중간 지점

			if (deque.size() % 2 == 0) {
				half_idx = deque.size() / 2 - 1;		// 만약 현재 덱의 원소가 짝수 개라면 중간 지점을 현재 덱의 절반 크기에서 -1 감소
			} else {
				half_idx = deque.size() / 2;
			}
			
			// 중간 지점 또는 중간 지점보다 원소의 위치가 앞에 있을 경우
			if (target_idx <= half_idx) {
				for (int j = 0; j < target_idx; j++) {		// 2번 연산 : idx 보다 앞에 있는 원소들을 모두 뒤로 보낸다. 
					int temp = deque.pollFirst();
					deque.offerLast(temp);
					count++;
				}
                
             // 중간 지점보다 원소의 위치가 뒤에 있는 경우    
			} else {		
				for (int j = 0; j < deque.size() - target_idx; j++) {		// 3번 연산 : idx를 포함한 뒤에 있는 원소들을 모두 앞으로 보낸다. 
					int temp = deque.pollLast();
					deque.offerFirst(temp);
					count++;
				}
			}
            
			deque.pollFirst();	// 1번 연산 : 연산이 끝나면 맨 앞 원소를 삭제
		}
		
		System.out.println(count);
	}
}

• half_idx = deque.size() / 2 - 1;

  • -1을 하는 이유

    • {1, 2, 3, 4} 일 때, 2를 중간지점으로 하면 인덱스는 1이기 때문

  • size() : 컬렉션프레임워크 타입의 길이를 알고자 할 때

    참고: length, length(), size()

• indexOf() : 해당 문자열에서 특정 문자나 문자열이 처음으로 등장하는 위치의 인덱스를 반환

  참고: String 클래스

• Deque(덱)을 이용한 문제

  • 메소드
    • pollFirst(), offerLast(), pollLast(), offerFirst()

  참고: 자바 컬렉션 (Java Collection, 컬렉션 프레임워크) - (5) Deque

• 3가지 연산 (이 中 2, 3번 연산을 최소화하도록)

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

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

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

• 예시

  • Deque = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 뽑을 숫자 : 1, 2, 3 일 때

    • 1번 연산 : 연속 3번
    • 2번 연산 : 0번
    • 3번 연산 : 0번

    2, 3번 연산 실행 횟수? 0번

  • Deque = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 뽑을 숫자 : 2, 9, 5 일 때

    • 2번 연산 : 1번 {2, 3, 4, 5, 6, 7, 8, 9, 10, 1}
    • 1번 연산 : 1번 '2'뽑기 {3, 4, 5, 6, 7, 8, 9, 10, 1}
    • 3번 연산 : 3번 {9, 10, 1, 3, 4, 5, 6, 7, 8}
    • 1번 연산 : 1번 '9'뽑기 {10, 1, 3, 4, 5, 6, 7, 8}
    • 3번 연산 : 4번 {5, 6, 7, 8, 10, 1, 3, 4}
    • 1번 연산 : 1번 '5'뽑기 {6, 7, 8, 10, 1, 3, 4}

    2, 3번 연산 실행 횟수? 1 + 3 + 4 = 8번

• LinkedList : 양방향을 위해 사용

---

참고: [백준] 1021번 : 회전하는 큐 - JAVA [자바]

---

회전하는 큐 (백준 1021번)