[알고리즘] 백준 2212 센서 Java

문제 정보

플랫폼 : 백준
분류 : 그리디 알고리즘
난이도 : 골드5
링크 : https://www.acmicpc.net/problem/2212

입력 데이터와 시간제한 검증

입력 데이터 갯수 : 1만 > Scanner
O(nlogn) 풀이 (정렬): 시간제한 ok
자료형 : 최대 100만 > int사용

풀이

처음 봤을 때 문제 이해가 힘들었다. 예시 InputData를 기준으로, 아래와 같은 맥락이다.

즉, k개의 집중국으로 모든 센서를 커버할 수 있도록 하는 각 집중국 범위의 합 을 구하는 문제이다.

주의해야 할 사항이 있는데, 집중국의 갯수(k)가 센서의 갯수 (n)보다 크거나 같은 경우 이다. 이는, 각각의 집중국이 각각의 센서를 담당하면 되므로, 각 집중국의 거리는 0이고, 합 또한 0이다.

알고리즘은 다음과 같다.
1) 입력을 받는다.
2) 만약 집중국 갯수(k) >= 센서 갯수(n)이면, 0을 출력하고 종료한다.
3) 센서의 거리를 오름차순으로 정렬한다. (순서대로 배치)
4) 각 센서 거리의 차이를 담은 배열을 만든다.
5) 차이 배열을 내림차순으로 정렬한다.
6) 차이 배열의 k-1 ~ 마지막 까지의 합을 출력한다.

4,5번이 이해가 되지 않을 수 있어 부가설명을 해보겠다.
위 그림을 보자.
센서 배열은 [1, 3, 6, 6, 7, 9]이다.
차이 배열 (이하 diff배열)은 [2, 3, 0, 1, 2] 이다.
집중국(k)는 2 이므로, 센서와 센서 사이를 1회 뛰어넘을 수 있다. (=diff배열에서 하나를 제외할 수 있다.)
만약 집중국(k)가 3개라면, 센서와 센서 사이를 2회 뛰어넘을 수 있고 그 그림은 아래와 같다. (3~6 구간, 7~9구간을 뛰어넘었다.)

문제에서 '최소 합'을 구하라 했으니, 내림차순으로 정렬하여 제일 높은 부분을 뛰어넘고 나머지의 합을 구한다.

코드

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//1. 입력을 받는다.
		int n = sc.nextInt(); // 센서의 갯수
		int k = sc.nextInt(); // 집중국의 갯수
		//2. 만약 집중국 갯수(k) >= 센서 갯수(n)이면, 0을 출력하고 종료한다.
		if(k >= n) {
			System.out.println(0);
			return;
		}
		int sum = 0;
		
		//1. 입력을 받는다
		int[] sensorArr = new int[n];
		for(int i = 0; i < n; i++)
			sensorArr[i] = sc.nextInt();
		
		//3. 센서의 거리를 오름차순으로 정렬한다. (순서대로 배치)
		Arrays.sort(sensorArr);
		
		//4. 각 센서 거리의 차이를 담은 배열을 만든다.
		Integer[] diffArr = new Integer[n-1];
		for(int i = 0; i < n-1; i++)
			diffArr[i] = sensorArr[i+1] - sensorArr[i];
		
		//5. 차이 배열을 내림차순으로 정렬한다.
		Arrays.sort(diffArr, Collections.reverseOrder());
		
		//6. 차이 배열의 k-1 ~ 마지막 까지의 합을 출력한다.
		for(int i = k-1; i < n-1; i++) {
			sum += diffArr[i];
		}
		System.out.println(sum);
	}
}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.