[백준 / 골드5] 2212 센서 (Java)

문제 보기

사용한 것

• 길이가 긴 구간을 우선적으로 건너뛰기 위한 그리디
• 센서 조합의 시작 좌표와 마지막 좌표로 효율적으로 구현하기 위한 투포인터

풀이 방법

하나의 집중국이 여러 센서를 가지고 있는 조합이라고 생각하자.
각 조합들의 거리를 최대한 멀게 설정하면 집중국의 수신 가능 영역의 합이 최소화된다.

• 입력 받은 센서의 좌표를 배열 arr에 저장하고 오름차순 정렬한다.
  
  
• 2차원 diff 배열을 만든다(원소의 0번째 인덱스 : 센서의 좌표, 1번째 인덱스 : 다음 센서 좌표와의 거리)
• arr을 for 문 돌며 diff를 초기화한다.
• diff를 다음 센서 좌표와의 거리로 내림차순 정렬한다.
• diff를 for 문 돌며 skipIdx에 가장 거리가 먼 k-1개의 구간 시작점을 저장한다. (마지막 구간은 건너뛸 필요 없으므로 k-1)
  
  
• arr로 투포인터를 사용하여 건너뛸 구간이면 해당 조합의 수신 가능 영역을 answer에 더하고 l을 다음 좌표로 바꾼다.
• for 문이 끝나면 마지막 조합의 수신 가능 영역을 answer에 더하고 출력한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();

        // 간격 내림차순 k - 1개 저장
        k = Math.min(n, k);
        Arrays.sort(arr);
        int[][] diff = new int[n - 1][2];
        for (int i = 0; i < n - 1; i++) {
            diff[i][0] = arr[i];
            diff[i][1] = arr[i + 1] - arr[i];
        }
        Arrays.sort(diff, (o1, o2) -> o2[1] - o1[1]);
        Set<Integer> skipIdx = new HashSet<>();
        for (int i = 0; i < k - 1; i++) {
            skipIdx.add(diff[i][0]);
        }

        // 그리디
        int answer = 0;
        int l = arr[0];
        int r = arr[0];
        for (int i = 0; i < n; i++) {
            r = arr[i];

            if (skipIdx.contains(r)) {
                answer += r - l;
                l = arr[i + 1];
            }
        }
        answer += r - l;

        System.out.println(answer);
    }
}