(JAVA) 백준 2212번 : 센서 --- [그리디]

www.acmicpc.net/problem/2212

2212번: 센서

 

안녕하세요.

 

그리디 알고리즘 문제입니다.

 

처음 문제를 읽었을 때, 문장이 어렵게 적혀있어서 이해하느라 애먹었네요..

 

 

백준에 해당 질문과 답을 보고 이해했습니다. 참고하실 분 참고하세요!

www.acmicpc.net/board/view/46572

글 읽기 - 문제 설명이 모호해서 헷갈립니다..

 

정리하자면,

 

 

입력 예제가 

 

6

2

1 6 9 3 6 7

 

이 있을 때,

집중국은 2개를 설치할 수 있습니다.

그럼, 1 3 6 6 7 9 좌표에 센서들이 있다면,

2좌표, 7좌표에 하나씩 설치하면 범위가 1, 2로 1+2 = 3 이 정답이 아니냐?

 

라고 헷갈렸습니다.

 

하지만, 이렇게 센서 사이 특정 좌표에 집중국을 설치하는게 아니라

센서를 집중국 개수만큼 집합하면 됩니다. 즉, 묶으면 됩니다.

[1, 3] 과 [6, 9] 로 묶으면 범위가 2 + 3 = 5 로 최소이고, 곧 정답입니다.

 

 

 

그럼, 바로 솔루션 들어가겠습니다.

솔루션

---

입력 예제가

 

6

2

1 6 9 3 6 7

 

이 있을 때.

 

 

  1)  센서 좌표 값 배열(Array가 List보다 더 빠름) 에 담기

    -> 집중국을 설치하기 위해 구역을 찾아야 합니다.

 

  2)  센서 좌표 값 배열 오름차순 정렬

    ->  1)과 일치

 

  3)  센서 사이 간격 값 구해서 오름차순 정렬

    ->  간격을 알아야, 최소합을 찾을 수 있습니다.

 

  4)  가장 높은 간격 값부터 K - 1(집중국 개수 - 1) 개를 전부 0으로 만듬

    ->  K - 1개를 0으로 만드는 이유는, 위 예시에서 [1, 3] 과 [6, 9] 두 구역을 나눴을 때, 3과 6 사이 간격은 고려하지 않습니다. 3과 6 사이가 3으로 모든 간격 값 중 가장 높은 값이었죠.

 

즉, 집중국을 놓을 때 두 센서를 하나의 구역에 포함시키지 않고 분리했으므로 두 센서 사이 간격은 무시됩니다. 이를 응용한다면, 가장 간격이 높은 값을 기준으로 분리시켜 구역을 만들면 최소합이 나오겠죠?

 

  5)  모든 간격 값 더하기

 

 

이 때, 4)와 5)를 하나의 for문으로 수행할 수 있습니다. 즉, 간격 배열을 오름차순 정렬헀을 때, index 0부터 시작해서 N - K개를 순환하면 됩니다!

 

 

 

 

이상입니다.

 

감사합니다!

 

*** 참고로, 소스코드에는 List와 Array 두 가지 방법의 해설이 있습니다. 채첨 결과, Array가 메모리 / 속도 측면에서 훨씬 우수했습니다!

소스코드

---

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Arrays;
	import java.util.StringTokenizer;
	// 센서
	// 그리디 알고리즘
	public class p2212 {
	public static void main(String args[]) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.valueOf(br.readLine());
	int k = Integer.valueOf(br.readLine());
	/* 1. ArrayList 활용 */
	/*List<Integer> sensors = new ArrayList<Integer>();
	List<Integer> distances = new ArrayList<Integer>();
	StringTokenizer st = new StringTokenizer(br.readLine());
	for(int i = 0; i < n; i++) {
	int num = Integer.valueOf(st.nextToken());
	sensors.add(num);
	}
	// 1) 센서 좌표 오름차순
	Collections.sort(sensors);
	// 2) 양 사이 간격 값 구해서 오름차순
	for(int i = 0; i < n - 1; i++) {
	int distance = sensors.get(i + 1) - sensors.get(i);
	distances.add(distance);
	}
	Collections.sort(distances);
	// 3) 인덱스 0부터 시작해서, (간격 값 개수 - 1) - (K - 1) 까지 더하기
	int len = distances.size(); // n - 1개
	int sum = 0;
	for(int i = 0; i < len - (k - 1); i++) {
	sum += distances.get(i);
	}*/
	/* 2. Array 활용 -> 훨씬 빠르다. */
	int[] sensors = new int[n];
	int[] distances = new int[n - 1];
	StringTokenizer st = new StringTokenizer(br.readLine());
	for(int i = 0; i < n; i++) {
	int num = Integer.valueOf(st.nextToken());
	sensors[i] = num;
	}
	// 1) 센서 좌표 오름차순
	Arrays.sort(sensors);
	// 2) 양 사이 간격 값 구해서 오름차순
	for(int i = 0; i < n - 1; i++) {
	int distance = sensors[i + 1] - sensors[i];
	distances[i] = distance;
	}
	Arrays.sort(distances);
	// 3) 인덱스 0부터 시작해서, (간격 값 개수 - 1) - (K - 1) 까지 더하기
	// int len = n - 1; // n - 1개
	int sum = 0;
	for(int i = 0; i < n - k; i++) {
	sum += distances[i];
	}
	System.out.println(sum);
	}
	}

view raw p2212.java hosted with ❤ by GitHub