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

풀이 ① - SensorDistance[] 정의

1. 아이디어

• 인접한 센서 간 거리가 먼 곳에 집중국을 설치해나감
  => 인접한 센서 간 거리가 가장 먼 곳들을 분리하여, 집중국을 할당하는 느낌
  
  

1) 센서 배열을 센서 위치 빠른 순으로 정렬

2) 인접 센서 간 거리를 계산하여 배열에 저장 후, 거리 큰 순으로 정렬

• SensorDistance[]
  => SensorDistance: 2개 센서 번호 (sensor1, sensor2), 2개 센서의 거리 distance

3) 정렬된 센서 간 거리 배열에서 큰 거리 순으로 (k-1) 개 선택

• 집중국 설치, 센서 영역 분할
• List<Integer>에 SensorDistance[]의 각 원소에서 sensor1 저장

2. 자료구조

• SensorDistance[]: 인접 센서 간 거리, 2개 센서 번호 저장한 배열
• List<Integer>, ArrayList<Integer>: 집중국 설치할 위치 (거리가 먼 인접 센서 분할) 저장

3. 시간 복잡도

• 센서 빠른 위치 순으로 정렬: O(n log n)
• 인접 센서 간 거리 배열 정렬: O(n log n)
• 영역 최소 합 계산: O(2k)

=> 총 시간 복잡도: O(2n log n + 2k)
=> n, k 최대값 대입: 대충 (2 x 10^5 + log 2^13) + (2 x 10^3)
= (26 x 10^5) + (2 x 10^3) = (26 x 10^5) + (2 x 10^3) << 2억

코드

import java.io.*;
import java.util.*;

class SensorDistance implements Comparable<SensorDistance> {
	public int sensor1, sensor2;
	public int distance;

	public SensorDistance(int sensor1, int sensor2, int distance) {
		this.sensor1 = sensor1;
		this.sensor2 = sensor2;
		this.distance = distance;
	}

	public int compareTo(SensorDistance sd) {
		int distanceDiff = sd.distance - this.distance;
		if (distanceDiff != 0)		// 거리 큰 순
			return distanceDiff;
		else						// 거리가 같으면, sensor 번호가 빠른 순
			return this.sensor1 - sd.sensor1;
	}
}

public class Main {
	static int n, k;				// 센서 개수 n, 집중국 개수 k
	static int[] sensors;			// 각 센서의 위치
	static int minSum;				// 출력: 영역 길이 최소 합

	static SensorDistance[] sds;	// 인접한 센서 간 거리
	static List<Integer> herbList = new ArrayList<>();

	static void solution() {
		// 인접 센서 간 거리 큰 순으로 (k-1)개 선택
		for (int i = 0; i < k - 1; i++)
            herbList.add(sds[i].sensor1);

		// 각 집중국의 영역 계산
		int startIdx = 0;
		for (int herbIdx : herbList) {
			minSum += (sensors[herbIdx] - sensors[startIdx]);
			startIdx = herbIdx + 1;
		}
		minSum += (sensors[n - 1] - sensors[startIdx]);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

		sensors = new int[n];
		sds = new SensorDistance[n - 1];
		for (int i = 0; i < n; i++)
			sensors[i] = Integer.parseInt(st.nextToken());

		// 예외 처리) 집중국 개수 k >= 센서 개수 n 인 경우, 센서마다 집중국 설치
		if (k >= n) {
			System.out.println(0);
			return;
		}

		Arrays.sort(sensors);		// 센서 위치 빠른 순으로 정렬

		// 인접 센서 간 거리 저장
		for (int i = 1; i < n; i++) {
			sds[i - 1] = new SensorDistance(
					i - 1, i, Math.abs(sensors[i - 1] - sensors[i])
			);
		}

		Arrays.sort(sds);			// 인접 센서 간 거리 큰 순으로 정렬

		solution();
		System.out.println(minSum);
	}
}

풀이 ② - Integer[]에 거리만 저장

1. 아이디어

• 인접한 센서 간 거리가 먼 곳에 집중국을 설치해나감
  => 인접한 센서 간 거리가 가장 먼 곳들을 분리하여, 집중국을 할당하는 느낌
  
  

1) 센서 배열을 센서 위치 빠른 순으로 정렬

2) 인접 센서 간 거리를 계산하여 배열에 저장 후, 거리 큰 순으로 정렬

• Integer[] distances

3) 정렬된 센서 간 거리 배열에서 큰 거리 순으로 (k-1) 개 제외하고, 나머지 거리들을 모두 더한 값이 최소 합

• 정렬된 배열에서 distances[0] ~ distances[k-2] 는 합에서 제외

  "집중국을 설치한다"
  = "해당 인접 센서 간의 거리는 합에서 제외한다"

• distances[k-1] ~ distances[끝] 까지 모든 거리들을 더함

2. 자료구조

• Integer[]: 인접 센서 간 거리 배열
  => 값이 큰 순으로 정렬하기 위해 int[]가 아닌, Integer[] 사용

3. 시간 복잡도

• 센서 빠른 위치 순으로 정렬: O(n log n)
• 인접 센서 간 거리 배열 정렬: O(n log n)
• 영역 최소 합 계산: O(k)

=> 총 시간 복잡도: O(2n log n + k)
=> n, k 최대값 대입: 대충 (2 x 10^5 + log 2^13) + 10^3
= (26 x 10^5) + 10^3 = (26 x 10^5) + 10^3 << 2억

코드

import java.io.*;
import java.util.*;

public class Main2 {
	static int n, k;				// 센서 개수 n, 집중국 개수 k
	static int[] sensors;			// 각 센서의 위치
	static Integer[] distances;		// 인접 센서 간 거리
	static int minSum;				// 출력: 영역 길이 최소 합

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

		sensors = new int[n];
		distances = new Integer[n - 1];
		for (int i = 0; i < n; i++)
			sensors[i] = Integer.parseInt(st.nextToken());

		// 예외 처리) 집중국 개수 k >= 센서 개수 n 인 경우, 센서마다 집중국 설치
		if (k >= n) {
			System.out.println(0);
			return;
		}

		Arrays.sort(sensors);		// 센서 위치 빠른 순으로 정렬

		// 인접 센서 간 거리 저장
		for (int i = 1; i < n; i++)
			distances[i - 1] = Math.abs(sensors[i - 1] - sensors[i]);

		Arrays.sort(distances, Collections.reverseOrder());		// 인접 센서 간 거리 큰 순으로 정렬
//		Arrays.sort(distances, (d1, d2) -> d2 - d1);

		// 인접 센서 간 거리 큰 순으로 (k-1)개 제외하고, 나머지 모두 더함
		for (int i = k - 1; i < n - 1; i++)
			minSum += distances[i];

		System.out.println(minSum);
	}
}