백준 2212번: 센서

 

문제 풀이

1. 정렬: 먼저, 센서들의 좌표를 정렬합니다. 이렇게 해야 집중국을 배치할 때 자연스럽게 가장 가까운 센서끼리 묶을 수 있습니다.
2. 간격 계산: 센서들이 정렬되면, 각 센서 간의 간격을 구할 수 있습니다. 이를 통해 집중국이 필요 없는 구간을 최소화하려면, 간격이 큰 구간부터 나누는 것이 유리합니다. 예를 들어, 가장 큰 간격을 차지하는 구간을 나누면, 그 나머지 구간들은 집중국의 수신 범위 내에 포함될 가능성이 높아집니다.
3. 간격을 나누기: 간격을 K-1개로 나누면, K개의 집중국을 만들 수 있습니다. 간격을 나누는 방식은 큰 간격을 우선적으로 나누는 것입니다. 이때, 나누어진 간격을 빼면 수신 가능 영역의 길이의 합을 최소화할 수 있습니다.

 

코드 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 센서의 개수 N, 집중국의 개수 K
        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);

        // 만약 K가 N보다 크거나 같으면, 각 센서마다 집중국을 둘 수 있으므로, 길이가 0인 영역이 생기게 됨.
        if (K >= N) {
            System.out.println(0);
            return;
        }

        // 센서들 간의 간격 차이를 구한다.
        List<Integer> gaps = new ArrayList<>();
        for (int i = 1; i < N; i++) {
            gaps.add(sensors[i] - sensors[i - 1]);
        }

        // 간격을 내림차순으로 정렬 (가장 큰 간격부터 나누기 위해)
        Collections.sort(gaps, Collections.reverseOrder());

        // K-1개의 큰 간격을 제외한 나머지 간격들을 더해서 최소 수신 영역 길이 합을 구한다.
        int totalLength = sensors[N - 1] - sensors[0];
        for (int i = 0; i < K - 1; i++) {
            totalLength -= gaps.get(i);
        }

        System.out.println(totalLength);
    }
}

 

 

시간 복잡도

• 센서의 개수 N에 대해, 센서들을 정렬하는 데 O(N log N)이 걸리고, 그 후에 간격을 계산하는 데 O(N) 시간이 소요됩니다. 따라서 전체 시간 복잡도는 **O(N log N)**입니다.