백준 - 13164

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[] height = new int[N-1];
		st = new StringTokenizer(br.readLine());
		int bef = Integer.parseInt(st.nextToken());
		for(int i = 0; i < N-1; i++) {
			int num = Integer.parseInt(st.nextToken());
			height[i] = num - bef;
			bef = num;
		}
		Arrays.sort(height);
		int sum = 0;
		for(int i = 0; i < N - K; i++) {
			sum += height[i];
		}
		System.out.println(sum);
	}
}

풀이과정 및 리뷰

• 문제 접근: 오름차순으로 정렬되어 입력되므로 입력값을 [i+1] - [i]로 빼서 둘 사이의 차이를 구해 배열에 저장한 후 이를 사용해서 최소값을 구한다.

  → “가장 큰 차이 (K-1개)를 제외한 나머지를 모두 더하면 최소합이 된다”
  

• 시간복잡도: $O(N log N)$

  • 인접 차이 계산: O(N)
  • 정렬: O(N log N)
  • 합 계산: O(N)

• 풀이과정

  • 테스트 케이스 5 3 / 1 3 5 6 10 을 각각의 자릿수 차이만큼 배열로 저장 [2,2,1,4]
  • 이후 해당 배열 height 을 정렬한 후 , 0 ~ N - K - 1 만큼 순회하며 sum에 누적합 저장

• 개선점

  정렬 없이 힙(우선순위 큐) 사용 고려

  • Arrays.sort() 대신 우선순위 큐(PriorityQueue) 사용 시, 가장 작은 N-K개의 합만 필요한 경우 성능 최적화 가능 (특히 큰 입력일 때).

    예:

    PriorityQueue<Integer> pq = new PriorityQueue<>();
    // add all diffs
    for (...) pq.add(diff[i]);
    // sum the N - K smallest
    for (int i = 0; i < N - K; i++) sum += pq.poll();

    하지만 이 문제는 N <= 10^5 수준이면 정렬이 더 간단하고 충분히 빠릅니다.