문제

https://www.acmicpc.net/problem/1021

풀이

나는 이 문제를 큐(Queue)를 이용하여 해결하였다.

큐의 가장 큰 특징은 리스트의 첫 번째 값을 출력하거나 제거할 수 있고, 리스트의 마지막에 새로 추가한다는 것이다.

poll - 첫 번째 값을 반환하고 제거한다.
remove - 첫 번째 값을 제거한다.
peek - 첫 번째 값을 반환한다.

add - 리스트의 마지막에 값을 추가한다.
offer - 리스트의 마지막에 값을 추가한다.
둘의 차이는 add는 실패했을때 예외가 발생한다는 점??

이러한 특징을 이용하여 해결하였고 로직은 간단하다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Num1021 {

    public static int N;
    public static int M;
    public static int Num[];
    public static Queue<Integer> queue = new LinkedList<>();
    public static int count = 0;

    public static void main(String[] args) {
        //input
        Scanner scanner = new Scanner(System.in);
        String[] a = scanner.nextLine().split(" ");
        N = Integer.parseInt(a[0]);
        M = Integer.parseInt(a[1]);
        Num = new int[M];
        a = scanner.nextLine().split(" ");
        for (int i=0; i<M; i++) {
            Num[i] = Integer.parseInt(a[i]);
        }
        for (int i=1; i<=N; i++) {
            queue.add(i);
        }

        //logic
        for (int i=0; i<M; i++) {
            int frontCount = 0, backCount = 0;
            while (Num[i] != queue.peek()) {
                queue.add(queue.poll());
                frontCount++;
            }
            queue.poll();
            backCount = N - frontCount;
            count += Math.min(backCount, frontCount);
            N--;
        }

        //output
        System.out.println(count);
    }
}