[BOJ] 1021 - 회전하는 큐 (Java)

알고리즘

• 자료 구조
• 덱

1. 문제

• 큐에서 특정 위치의 요소를 효율적으로 찾아서 제거
  
  
  첫 줄 | N(큐의 크기), M(뽑아내려고 하는 수의 개수)
  두 번째 줄 | M개의 정수로, 뽑아내려는 수들
  deque = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  // 1을 뽑아낸다면
  deque = [2, 3, 4, 5, 6, 7, 8, 9, 10]
  // 2를 뽑아낸다면
  deque = [3, 4, 5, 6, 7, 8, 9, 10]
  ...

2. Idea

• 큐에서 요소를 뽑아내기 위해서는 그 요소가 현재 큐의 어느 위치에 있는지 알아야 함.
• 요소가 앞쪽에 있는 경우, 왼쪽에서 요소를 뽑아내는 연산(pollFirst)이 필요하고,
  그 요소 앞에 있는 모든 요소를 뒤로 이동(offerLast)시켜야 함
• 요소가 뒤쪽에 있는 경우, 오른쪽에서 요소를 뽑아내는 연산(pollLast)이 필요하고, 그
  요소 뒤에 있는 모든 요소를 앞으로 이동(offerFirst)시켜야 함
• 덱 사용
  • 덱은 양방향 회전이 가능하여, 목표 요소를 더 적은 연산으로 앞쪽이나 뒤쪽으로 이동시킬 수 있음
    -> 큐의 중간 지점을 기준으로 목표 요소가 앞쪽에 있는지 뒤쪽에 있는지를 판단하고, 그에 따라 최소한의 회전으로 요소를 찾을 수 있습니다.

3. 풀이

3.1. 변수 선언 및 초기화

• N: 큐의 크기
• M: 뽑아내려는 수의 개수
• seq: 뽑아내려는 수들을 저장할 배열

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());	// 뽑아내려고 하는 수의 개수

        // 1부터 N까지 덱에 넣어둠
        for(int i = 1; i <= N; i++) {
            deque.offer(i);
        }
        int[] seq = new int[M];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < M; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

3.2. 목표 수 위치 찾기 및 이동

• 목표 수의 현재 위치(target_idx)를 찾음
• 큐의 중간 인덱스(half_idx)를 계산
• target_idx가 중간보다 앞에 있는지 뒤에 있는가를 판단
  • 앞에 있을 경우) 목표 수 위치까지 왼쪽으로 이동(pollFirst 후 offerLast)
  • 뒤에 있을 경우) 목표 수 위치까지 오른쪽으로 이동(pollLast 후 offerFirst)
  • 이동할 때마다 count ++;
• 목표 수를 찾으면 pollFirst로 제거

        for(int i = 0; i < M; i++) {
            // 덱에서 뽑고자 하는 숫자의 위치(index) 찾기
            int target_idx = deque.indexOf(seq[i]);
            int half_idx;
            if(deque.size() % 2 == 0) {
                half_idx = deque.size() / 2 - 1;
            }
            else {
                half_idx = deque.size() / 2;
            }

            // 중간 지점 또는 중간 지점보다 원소의 위치가 앞에 있을 경우
            if(target_idx <= half_idx) {
                // 연산 2. idx 보다 앞에 있는 원소들을 모두 뒤로 보냄
                for(int j = 0; j < target_idx; j++) {
                    int temp = deque.pollFirst();
                    deque.offerLast(temp);
                    count++;
                }
            }
            else {	// 중간 지점보다 원소의 위치가 뒤에 있는 경우
                // 연산 3. idx를 포함한 뒤에 있는 원소들을 모두 앞으로 보냄
                for(int j = 0; j < deque.size() - target_idx; j++) {
                    int temp = deque.pollLast();
                    deque.offerFirst(temp);
                    count++;
                }
            }
            deque.pollFirst();	// 연산이 끝나면 맨 앞 원소를 삭제
        }

3.3. 결과 출력

• count 출력

System.out.println(count);

4. 전체코드

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

public class 1021.회전하는 큐{
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        LinkedList<Integer> deque = new LinkedList<Integer>();
        int count = 0;

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());	// 뽑아내려고 하는 수의 개수

        // 1부터 N까지 덱에 넣어둠
        for(int i = 1; i <= N; i++) {
            deque.offer(i);
        }
        int[] seq = new int[M];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < M; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < M; i++) {
            // 덱에서 뽑고자 하는 숫자의 위치(index) 찾기
            int target_idx = deque.indexOf(seq[i]);
            int half_idx;
            if(deque.size() % 2 == 0) {
                half_idx = deque.size() / 2 - 1;
            }
            else {
                half_idx = deque.size() / 2;
            }

            // 중간 지점 또는 중간 지점보다 원소의 위치가 앞에 있을 경우
            if(target_idx <= half_idx) {
                // 연산 2. idx 보다 앞에 있는 원소들을 모두 뒤로 보냄
                for(int j = 0; j < target_idx; j++) {
                    int temp = deque.pollFirst();
                    deque.offerLast(temp);
                    count++;
                }
            }
            else {	// 중간 지점보다 원소의 위치가 뒤에 있는 경우
                // 연산 3. idx를 포함한 뒤에 있는 원소들을 모두 앞으로 보냄
                for(int j = 0; j < deque.size() - target_idx; j++) {
                    int temp = deque.pollLast();
                    deque.offerFirst(temp);
                    count++;
                }
            }
            deque.pollFirst();	// 연산이 끝나면 맨 앞 원소를 삭제
        }
        System.out.println(count);
    }
}