2022.02.16 53일차

백준 1021번 (회전하는 큐)

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

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

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

나의 풀이

1. 첫 번째 원소를 제거, 큐 형태 - LinkedList 활용하기

2. 두 번째, 세번째가 나눠지는 기준 - list 중간값, 짝수와 홀수 생각하기
   ex) 짝수일 때
   [1, 2, 3, 4, 5, 6] - 가운데 인덱스 + 1 = 3
   인덱스가 3이하인 경우 두 번째 연산에 해당
   mid를 가운데 인덱스 + 1로 설정

   ex) 홀수일 때
   [1, 2, 3, 4, 5] - 가운데 인덱스 = 2
   인덱스가 2이하인 경우 두 번째 연산에 해당
   mid를 가운데 인덱스로 설정

3. 찾아야하는 값의 인덱스 target으로 설정, indexOf 활용

4. mid가 target보다 작거나 같은 경우
   세 번째 연산, list길이 - target 만큼 반복

5. mid가 target보다 큰 경우
   두 번째 연산, target 만큼 반복

6. 카운트 증가키면서 반복문 끝나면 list의 첫 번째 값 제거(poll 활용)

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        LinkedList<Integer> list = new LinkedList<>();
        for (int x = 1; x <= N; x++) {
            list.offer(x);
        }

        int count = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            int length = list.size();
            int mid = length % 2 == 0 ? length / 2 : length / 2 + 1;
            int target = list.indexOf(num);

            if (mid <= target) {
                for (int z = 0; z < length - target; z++) {
                    list.offerFirst(list.pollLast());
                    count++;
                }

            } else {
                for (int k = 0; k < target; k++) {
                    list.offerLast(list.pollFirst());
                    count++;
                }
            }

            list.poll();
        }

        System.out.println(count);
    }
}

생각하기

• LinkedList, 잦은 삽입과 삭제 시 사용하기