[백준] 1021번 회전하는 큐

yseo14·2024년 10월 7일

코딩테스트 대비

목록 보기

24/88

풀이

원소를 뒤 뿐만 아니라 앞에도 넣을 수 있어야하기 때문에 자료구조 Deque의 개념을 사용해서 풀이하면된다. 하지만 2, 3번 연산을 최소화하기 위해서 찾고자 하는 원소가 전체 원소 중에서 중간을 기준으로 왼쪽에 위치해있는지 오른쪽에 위치해있는지 인덱스를 통해 구분할 필요가 있다. 따라서 LinkedList를 사용한다.

코드

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

/**
 * 1. 첫번째 원소를 뽑아낸다 -> pollFirst()
 * 2. 왼쪽으로 한 칸 이동시킨다 -> pollFirst() 후 addLast()
 * 3. 오른쪽으로 한 칸 이동시킨다 -> pollLast() 후 addFirst()
 */

public class sol1021 {
    static int N, M;
    static LinkedList<Integer> deque = new LinkedList<>();
    static int result = 0;
    static int[] arr;

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

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

        arr = new int[M];

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

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

        for (int i = 0; i < M; i++) {
            int targetIndex = deque.indexOf(arr[i]);
            int halfIndex;
            if (deque.size() % 2 == 0) {	// 연결리스트 내 요소가 짝수개일 경우 -1 처리해준다.
                halfIndex = deque.size() / 2 - 1;
            } else halfIndex = deque.size() / 2;

            if (targetIndex <= halfIndex) {	//찾고자하는 원소의 인덱스가 중간인덱스보다 왼쪽에 있을 경우 
                moveLeft(targetIndex);
                deque.pollFirst();
            } else {	// 오른쪽에 있을 경우
                moveRight(deque.size() - targetIndex);
                deque.pollFirst();
            }
        }

        System.out.println(result);
    }

    public static void moveLeft(int n) {	//왼쪽으로 이동시키는 메서드
        while (n > 0) {
            deque.addLast(deque.pollFirst());
            result++;
            n--;
        }
    }

    public static void moveRight(int n) {	//오른쪽으로 이동시키는 메서드
        while (n > 0) {
            deque.addFirst(deque.pollLast());
            result++;
            n--;
        }
    }
}