백준 2212(JAVA)

문제

(너무 긴관계로 핵심만 딱 설명하겠다.)
직선위에 센서가 여러개 있다. 센서의 좌표는 정수로 입력되어진다.(일직선 위에 센서가 있는 것이다.) 센서의 개수는 N개이다.
해당 센서를 수신해야하는 집중국 K개를 세워야한다. 집중국들은 모든 센서를 수신하는 위치에 위치하여야한다. 여기서 문제!! 집중국이 센서로부터 수신 가능 영역의 길이합의 최소를 구하라

문제가 너무 난해하다 예제로 설명하겠다.
센서의 위치를 나타내는 정수
1 6 9 3 6 7
이를 오름차순 정렬하면
1 3 6 6 7 9
이중 집중국 2개를 설치해야하는데 센서 수신가능영역의 합을 최소로하라!
(1 3)을 수신하는 센서 1개 -> 영역의 길이 2
(6 9)를 수신하는 센서 1개 -> 영역의 길이 3
합 : 5

풀이

일단 오름차순한다음 적당한 K로 분할을 해야한다는 느낌이 퐉 온다!!
분할을 어떻게 할까 고민하며 예제를 혼자 만들며 문제를 풀어가는도중.. 나는 이러한 예제를 만들게 된다.
1 2 10 11 20 21
K가 2일때 어떻게 해야 영역의 합이 최소일까?

(1 2), (10 21) 일까?
(1 11), (20, 21)일까?
신기하게도 둘의 차이는 존재한다
전자는 영역의합이 1 + 11 로 12이고
후자는 영역의 합이 10 + 1로 11이다.
아니 뭔차일까? 고민하며 오름차순으로 정렬한 녀석의 차이를 한번 써봤다.(A4에 써가면서 풀었다.)

1 2 10 11 20 21
1 8 1 9 1
어? 8과 9의 차이로 답이 갈라지는구나 라는 느낌이 팍 들었다.
이걸 보자마자 아~~ 차이의 제일 큰녀석을 집중국의 개수 - 1만큼 빼주면 되는구나.
이 아이디어를 떠올리자 마자 문제를 쉽게 풀었땅!

코드는 직접 짜면서 해보자!(힌투 : 우선순위 큐를 이용해서 쉽게 최대값을 골라보자~)

코드

package baekjoon.그리디;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main2212 {
    static int N, K;
    static List<Integer> list = new ArrayList<>();
    static List<Integer> diffList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++){
            list.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(list);
        diffList = new ArrayList<>(N); //실제값은 N보다 하나 적을 예정

        if(N == 1){
            System.out.println(0);
        }else{
            System.out.println(calculateMinDistance());
        }


    }
    static int calculateMinDistance(){
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

        for(int i = 1; i < N; i++){
            diffList.add(list.get(i) - list.get(i - 1));
        }

        for(int i = 0; i < diffList.size(); i++){
            pq.offer(diffList.get(i));
        }

        for(int i = 0; i < K - 1; i++){
            pq.poll();
        }

        return pq.stream().mapToInt(i -> i).sum();
    }
}