BOJ 1461

2020-07-23

위 문제는 백준 사이트의 알고리즘 1461 문제에 관한 설명입니다.

문제

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다.

세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다.

각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오.

세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다.

책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다.

그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

입력

첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다.

둘째 줄에는 책의 위치가 주어진다.

N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다.

책의 위치는 0이 아니며, 그 절댓값이 10,000보다 작거나 같다.

출력

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


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String[] str = br.readLine().split(" ");
 
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        str = br.readLine().split(" ");

        Queue<Integer> pos_q = new PriorityQueue<Integer>((x, y) -> y - x); // 양수와 음수를 저장할 우선순위 큐를 사용한다.
        Queue<Integer> neg_q = new PriorityQueue<Integer>();
 
        for (int i = 0; i < N; i++) {
            if (Integer.parseInt(str[i]) > 0) {
                pos_q.add(Integer.parseInt(str[i]));
            } else {
                neg_q.add(Integer.parseInt(str[i]));
 
            }
        }
        int element;
        int max = 0;
        int sum = 0;
        //양수 일때
        while (!pos_q.isEmpty()) {
            for (int i = 0; i < M; i++) {
                if (pos_q.isEmpty())
                    continue;
                element = pos_q.poll();
                if (i == 0) {
                    sum += Math.abs(element);
                    if (Math.abs(element) > max) {
                        max = Math.abs(element);
                    }
                }
            }
        }
        //음수 일때
        while (!neg_q.isEmpty()) {
            for (int i = 0; i < M; i++) {
                if (neg_q.isEmpty())
                    continue;
                element = neg_q.poll();
                if (i == 0) {
                    sum += Math.abs(element);
                    if (Math.abs(element) > max) {
                        max = Math.abs(element);
                    }
                }
            }
        }
        System.out.println(sum * 2 - max);
    }
}

도서관