[자바] 백준 2212번: 센서

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

2212번: 센서

---

설명

어느 한 영역에 집중국을 두 개 세우게 되면,

그 영역을 두 개의 영역으로 나눌 수 있게 된다.

그럼 집중국은 어디에 세우는게 좋을까?

->센서와 센서 사이 거리가 가장 긴 곳을 기준으로 영역을 나누면 될 것 같다.

->집중국이 K개면 거리가 가장 긴 K-1개의 영역을 선택하면 된다. 그럼 영역이 K개로 나뉘고 각각의 영역에는 집중국이 하나씩 있다고 생각하면 된다.

 

N개의 센서 정보를 입력 받고,

한 센서와 그 옆 센서와의 거리를 계산해서 어디엔가 기록해 둔다.

 

집중국에 영향을 받는 영역을 구하는 방법은

맨 뒤에 있는 센서 위치 - 맨 앞에 있는 센서 위치를 계산해서 총 영역을 계산하고,

아까 계산해두었던 센서와 센서 사이 거리 중 가장 큰 수부터 K-1개를 뽑아 총 영역에서 빼주면 된다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Vector;

public class P2212 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		int result=0;
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		if(N<=K) {
			System.out.println("0\n");
			return;
		}
		for(int i=0;i<N;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		
		result=arr[N-1]-arr[0];
		
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		//센서와 센서 사이 거리값을 넣을 우선순위 큐. (내림차순)
		
		for(int i=0;i<N-1;i++) {
			pq.add(arr[i+1]-arr[i]);
		}
		for(int i=0;i<K-1;i++) {
			result-=pq.poll();
		}
		System.out.println(result);
		br.close();
	}

}

센서 위치 기준으로 오름차순 정렬하기 위해 배열 arr[N]을 생성해서 사용했다.

센서와 센서 사이 거리를 계산하고 기록해 둘 구조는 우선순위 큐가 좋을것같았다.

(그냥 배열에 넣고 정렬해도 됨)

거리가 큰 것부터 K-1개를 골라야 하기 때문에, 우선순위 큐가 내림차순으로 되게 설정했다.

 

.

.

 

처음에 코드를 작성해서 냈는데 검사결과 100%에서 nullpointer 에러가 떴다.

어디가 문제인가 곰곰이 생각해봤는데,

 

N보다 K가 클 때 (센서 개수보다 집중국의 수가 많을 때) 문제가 된다.

if(N<=K) {
			System.out.println("0\n");
			return;
		}

그래서 추가한 것이 이 코드이다.

 

N개의 센서가 있을 때, 센서와 센서 사이의 간격은 총 N-1개가 생긴다.

그런데 K-1번 pop을 하기 때문에, N-1 < K-1이면 문제가 발생한다(큐가 비어있어서 null을 반환함)

그리고 N<=K일 경우에는, 각각의 센서 위치에 집중국을 하나씩 세우면 되니 결과값은 0이 될 수 있다.

 

---

- PriorityQueue 내림차순으로 생성하는 법

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		//센서와 센서 사이 거리값을 넣을 우선순위 큐. (내림차순)

 Collections.reverseOrder메소드를 이용하여 생성함.