[백준 문제 풀이] 25305번 커트라인

Junu Kim·2025년 12월 26일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

69/89

[25305] 커트라인

난이도: ★☆☆☆☆ • solved on: 2025-12-26

문제 요약

문제 유형: 정렬, 선택(Selection)
요구사항: 점수 N개 중 내림차순으로 정렬했을 때 K번째 점수(커트라인)를 출력해야 한다.

사용 개념

자료구조
- PriorityQueue<Integer> (최대 힙처럼 사용)
- int[] 배열
알고리즘/기법
- 힙 (Heap) 기반 선택
- 정렬 (Sorting)
- 카운팅 (Counting) 기반 선택
핵심 키워드
- K-th largest (내림차순 K번째)
- cutline

풀이 아이디어 및 코드

방법 1 : PriorityQueue(최대 힙)로 K번째 뽑기 (사용자 풀이, 수정 금지)

문제 분해

모든 점수를 우선순위 큐(내림차순)로 넣는다.

poll()을 K-1번 수행하면, 다음 poll()이 K번째로 큰 점수이다.
핵심 로직 흐름
maxHeap에 모든 점수 삽입
(k-1)번 poll
다음 poll 값 출력
예외 처리

없음 (K는 1 이상, N 이하)

import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] cmds = sc.nextLine().split(" ");
        int n = Integer.parseInt(cmds[0]);
        int k = Integer.parseInt(cmds[1]);
        String[] nums = sc.nextLine().split(" ");
        PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
        for(String num : nums) {
            q.add(Integer.valueOf(num));
        }
        for(int i = 0; i < k-1; i++){
            q.poll();
        }
        System.out.println(q.poll());
    }
}

방법 2 : 배열 정렬 후 인덱스로 접근

문제 분해

점수를 배열에 담고 Arrays.sort()로 오름차순 정렬한다.

오름차순에서 N-K 인덱스가 “내림차순 K번째”와 동일하다.
핵심 로직 흐름
scores 정렬(오름차순)
출력 = scores[n - k]
예외 처리

없음

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

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[] a = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(a);                 // 오름차순
        System.out.println(a[n - k]);   // 내림차순 K번째
    }
}

방법 3 : 카운팅 기반 선택 (점수 범위가 작을 때 깔끔)

점수의 최댓값 범위가 크지 않으면 (이 문제는 점수 범위가 작게 주어지는 편) 정렬 없이도 가능하다.

점수별 빈도를 count[score]에 저장

큰 점수부터 내려오며 누적합이 K 이상이 되는 순간의 점수가 정답

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

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());

        // 점수 범위가 0~10000이라고 가정(문제 조건에 맞춰 배열 크기 설정)
        int[] cnt = new int[10001];

        st = new StringTokenizer(br.readLine());
        int max = 0;
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            cnt[x]++;
            if (x > max) max = x;
        }

        int acc = 0;
        for (int score = max; score >= 0; score--) {
            acc += cnt[score];
            if (acc >= k) {
                System.out.println(score);
                return;
            }
        }
    }
}

시간·공간 복잡도

방법 1 (PriorityQueue)

시간 복잡도: O(N log N)
공간 복잡도: O(N)

방법 2 (정렬)

시간 복잡도: O(N log N)
공간 복잡도: O(N) (입력 배열)

방법 3 (카운팅)

시간 복잡도: O(N + U) (U = 점수 범위)
공간 복잡도: O(U)

어려웠던 점

정렬을 실제로 구현할지 아니면 정렬은 내장된 정렬 함수 및 자료구조를 이용할지 문제에서 요구하는 수준이 어느정도인지 고민을 했다

배운 점 및 팁

아래와 같은 경우에만 실제로 정렬 알고리즘을 구현하기로 정리했다
- 문제에 “정렬 알고리즘을 구현하라” 같은 문구가 있는 경우
- 특정 제약 때문에 표준 정렬로는 비효율적이라서, 카운팅 정렬/기수 정렬(radix sort) 같은 범위 기반/자릿수 기반 정렬이 사실상 필수인 경우