백준 1461번 도서관 (JAVA)

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

1461번: 도서관

 

저는 우선순위 큐를 통해 문제를 해결하였습니다.

저는 음수 양수 따로 우선순위 큐를 만들고 우선순위 큐를 통해 절대값이 큰 수 부터 나오도록 하였습니다.

처음에 양수와 음수 가장 큰 절대값을 비교하여 더 큰 값을 저장합니다.

각각의 우선순위 큐에서 하나 빼고 이 값의 2배를 결과값에 더하고, 이후 m-1개를 그냥 빼 버리고, 이 행동을 우선순위 큐가 비어질 때 까지 진행합니다.

(2배를 곱하는 이유는 갔다가 와야하기 때문입니다.)

처음에 구한 양수와 음수 가장 큰 절대값 중 더 큰 값을 결과값에서 빼 답을 구하였습니다.

(다 정리하고 다시 돌아올 필요가 없기 때문입니다.)

 

package BOJ.dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1461 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int[] positions = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n ; i++){
            positions[i] = stoi.apply(st.nextToken());
        }
        int result = cal(positions,n,m);
        System.out.println(result);
    }

    private static int cal(int[] positions, int n, int m) {
        PriorityQueue<Integer> positive = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> negative = new PriorityQueue<>();
        for(int position : positions){
            if(position > 0){
                positive.add(position);
            }else{
                negative.add(position);
            }
        }
        positive.add(0);
        negative.add(0);
        int max = Math.max(Math.abs(positive.peek()),Math.abs(negative.peek()));
        int result = 0;
        while(!positive.isEmpty()){
            result += 2 * Math.abs(positive.poll());
            for(int i = 0 ; i < m - 1 ; i++){
                if(!positive.isEmpty()){
                    positive.poll();
                }
            }

        }
        while(!negative.isEmpty()){
            result += 2 * Math.abs(negative.poll());
            for(int i = 0 ; i < m - 1 ; i++){
                if(!negative.isEmpty()){
                    negative.poll();
                }
            }
        }
        result -= max;
        return result;
    }
}