BOJ 1461 도서관

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

문제

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

---

입력

첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.

---

출력

첫째 줄에 정답을 출력한다.

---

예제 입력 1

7 2
-37 2 -6 -39 -29 11 -28

예제 출력 1

131

예제 입력 2

8 3
-18 -9 -4 50 22 -26 40 -45

예제 출력 2

158

… 이하 예제 생략

---

코드

처음 볼 때는 간단하다고 생각했는데, 구현할 때 코드가 조금 더러워져서 은근히 시간이 많이 걸린 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int M;
    static PriorityQueue<Integer> leftBooks = new PriorityQueue<>();
    static PriorityQueue<Integer> rightBooks = new PriorityQueue<>(Comparator.reverseOrder());

    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());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int book = Integer.parseInt(st.nextToken());
            if(book > 0) {
                rightBooks.offer(book);
            } else {
                leftBooks.offer(book);
            }
        }

        int answer = calculateMinDistance();
        System.out.println(answer);
    }

    static int calculateMinDistance() {
        int movedDistance = 0;

        /**
         * 책을 제자리에 놔둔 후 다시 0으로 돌아올 필요가 없기 때문에
         * 가장 먼 거리에 있는 책을 놔두고 0으로 돌아오는 거리를 미리 차감하기 위해
         * 가장 왼쪽, 오른쪽에 있는 책 중 더 먼 거리를 미리 뺀다.
         */
        if(leftBooks.isEmpty() || !rightBooks.isEmpty() && Math.abs(leftBooks.peek()) < rightBooks.peek()) {
            movedDistance -= rightBooks.peek();
        } else {
            movedDistance -= Math.abs(leftBooks.peek());
        }

        // 왼쪽과 오른쪽에 있는 책을 놔두고 0으로 돌아오는 거리를 추가
        movedDistance += calculateMovedDistance(leftBooks);
        movedDistance += calculateMovedDistance(rightBooks);

        return movedDistance;
    }

    static int calculateMovedDistance(PriorityQueue<Integer> books) {
        int movedDistance = 0;

        while (!books.isEmpty()) {
            movedDistance += books.poll() * 2;
            for (int i = 1; i < M; i++) {
                books.poll();
            }
        }

        return Math.abs(movedDistance);
    }
}