백준 센서

목표

오늘은 백준에서 골드문제를 풀어봤는데 생각해야할 부분이 정말 많았던것같다. 골드이상 문제를 풀었을때 문제 없게 푸는게 목표이다.

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다.
셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다.
각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.
첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

내가 이 문제를 보고 생각해본 부분

집중국을 최적의 위치에 놓기 위해서는 센서간의 거리(갭)을 기준으로 판단하게 됐다.
가장 짧은 갭부터 집중국을 놓으면 그 지점에서 가장 많은 센서를 커버할 수 있다는 생각이 들었다.
따라서 센서 위치를 정렬하고 인접한 센서간의 갭을 구해 정렬한 후,
가장 짧은 K-1개의 갭을 선택하는 것이 최적의 방법이라 판단하게 됏다.

코드로 구현

package baekjoon.baekjoon_18;

import java.util.Arrays;
import java.util.Scanner;

// 백준 2212번 문제
public class Main649 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();

        int[] sensors = new int[N];
        for(int i = 0; i < N; i++) {
            sensors[i] = sc.nextInt();
        }

        Arrays.sort(sensors);

        int[] gaps = new int[N-1];
        for(int i = 0; i < N-1; i++) {
            gaps[i] = sensors[i+1] - sensors[i];
        }

        Arrays.sort(gaps);

        int result = 0;
        for(int i = 0; i < N-K; i++) {
            result += gaps[i];
        }

        System.out.println(result);
        sc.close();
    }
}

시간복잡도 O(NlogN)

장점
입력 데이터가 많아도 비교적 빠르게 수행할 수 있다.
N이 커질수록 정렬 알고리즘의 효율성이 사용할 수 있다.

단점
입력 데이터가 적은 경우에는 불필요한 정렬을 할 수 있다.
메모리를 추가 사용해야하는 단점이 있다.

마무리

오늘은 백준에서 골드문제를 풀었는데 문제 자체적으로 조금 어렵게 느껴졌다. 아직 연습부족이라고 생각하고 조금더 문제를 풀어봐야할것같다. 그리고 다른 방법으로 문제를 풀 수 있지 고민하고 구현해봐야겠다.