백준 25305 커트라인 Java: primitive 배열 정렬 오류를 바로잡은 풀이

백준 25305 커트라인 Java 풀이의 핵심은 점수를 정렬한 뒤 상위 K명의 마지막 점수를 찾는 것이다. 예전에 이 문제를 풀 때는 int[]를 내림차순으로 정렬하려고 Collections.reverseOrder()를 넘겼다가 컴파일 오류를 만났다. 곧바로 답을 검색하기보다 Arrays.sort의 overload를 읽어 보면서 primitive 배열과 객체 배열의 차이를 확인했던 기록이 남아 있다.

문제를 한 문장으로 바꾸기

응시자 N명의 점수 중 가장 높은 K개가 수상권이라면, 커트라인은 그 K개 중 가장 낮은 점수다.

예를 들어 점수가 다음과 같다고 하자.

100 76 85 93 98

오름차순으로 정렬하면 76 85 93 98 100이다. 상위 2명의 커트라인은 뒤에서 두 번째인 98이다.

정렬한 배열의 index는 0부터 시작하므로 답은 다음 위치에 있다.

scores[N - K]

굳이 내림차순 배열을 만들 필요가 없다.

int[]에 reverseOrder()를 쓸 수 없었던 이유

Java의 Arrays.sort에는 primitive 배열을 받는 overload와 객체 배열을 받는 generic overload가 따로 있다.

Arrays.sort(int[] array);
Arrays.sort(T[] array, Comparator<? super T> comparator);

Collections.reverseOrder()가 반환하는 값은 Comparator다. 따라서 Integer[] 같은 객체 배열에는 전달할 수 있지만 int[]에는 전달할 수 없다. Oracle Arrays 문서에서도 int[] 정렬은 오름차순 overload로, comparator를 받는 정렬은 T[] overload로 구분한다.

이 문제에서는 boxing 비용을 들여 Integer[]로 바꾸기보다 int[]를 오름차순 정렬하고 N - K 위치를 읽는 편이 더 단순하다.

Java 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        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[] scores = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            scores[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(scores);
        System.out.println(scores[n - k]);
    }
}

예제로 확인하기

입력:

5 2
100 76 85 93 98

출력:

98

경계도 index 식으로 바로 확인할 수 있다.

• K = 1이면 scores[N - 1], 즉 최고 점수다.
• K = N이면 scores[0], 즉 최저 점수다.

복잡도와 자료형

• 시간 복잡도: 정렬에 O(N log N)
• 공간 복잡도: 입력 배열에 O(N)
• 자료형: 점수와 index는 문제 범위에서 int로 충분하다.

당시에는 내림차순 정렬을 만드는 방법 자체에 시선이 먼저 갔다. overload를 직접 읽어 본 뒤에는 “원하는 순서”보다 “답이 정렬된 배열의 어느 위치인가”를 먼저 적는 습관이 더 중요하다는 쪽으로 생각이 바뀌었다.

정렬 뒤 양쪽 index를 움직이는 문제는 백준 3273 두 수의 합, 여러 정렬 방식의 선택 기준은 정렬 알고리즘 정리에서 이어서 볼 수 있다.

참고 자료

• 백준 25305: 커트라인
• Internet Archive: 백준 25305 문제 스냅샷
• Oracle Java 21: Arrays