자료구조 · 알고리즘 기초집LESSON 18

우선순위 큐와 힙: 최고 점수 랭킹을 효율적으로 관리하기

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

18강. 우선순위 큐와 힙: 최고 점수 랭킹을 효율적으로 관리하기

1. 이번 강의에서 해결할 문제

수백만 기록 중 상위 10개만 필요할 때 전체 목록을 모두 정렬하면 필요 이상의 시간과 메모리를 사용할 수 있습니다.

2. 학습 목표

3. 핵심 개념

우선순위 큐는 삽입 순서가 아니라 우선순위가 가장 높은 원소를 먼저 꺼냅니다. Java PriorityQueue는 기본적으로 최소 원소가 head인 힙 기반 구현입니다. 상위 K개를 구할 때 K 크기의 최소 힙을 유지하면 현재 상위 K 중 가장 작은 값을 빠르게 제거할 수 있습니다. 내부 배열 전체가 정렬되어 있다는 보장은 없습니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/TopKRanking.java

src/TopKRanking.java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class TopKRanking {
    record GameRecord(String playerId, int score) {}

    static List<GameRecord> topK(List<GameRecord> records, int k) {
        if (k <= 0) return List.of();
        PriorityQueue<GameRecord> heap = new PriorityQueue<>(Comparator.comparingInt(GameRecord::score));
        for (GameRecord record : records) {
            heap.offer(record);
            if (heap.size() > k) heap.poll();
        }
        List<GameRecord> result = new ArrayList<>(heap);
        result.sort(Comparator.comparingInt(GameRecord::score).reversed());
        return result;
    }

    public static void main(String[] args) {
        List<GameRecord> records = List.of(new GameRecord("P1", 900),
                new GameRecord("P2", 1500), new GameRecord("P3", 1200), new GameRecord("P4", 700));
        System.out.println(topK(records, 2));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/TopKRanking.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/TopKRanking.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\TopKRanking.java
java -cp .\out TopKRanking

예상 결과: 1500점 P2와 1200점 P3가 내림차순으로 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

각 기록을 힙에 넣고 크기가 K를 넘으면 가장 낮은 점수를 제거합니다. n개 처리 시간은 O(n log k), 결과 정렬 O(k log k), 공간 O(k)입니다. 전체 정렬 O(n log n)보다 K가 n보다 훨씬 작을 때 유리합니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ