24강. 최종 실습: 게임 기록 분석·랭킹 알고리즘 프로그램 완성하기

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

개별 알고리즘 예제를 하나의 프로그램으로 합치려면 원본 기록, 플레이어 색인, 점수 검색, 상위 랭킹, 스테이지 연결 탐색의 책임과 복잡도를 분리해야 합니다.

✓2. 학습 목표

✓이 강의를 마치면

• 요구사항별 자료구조와 알고리즘을 근거와 함께 선택합니다.
• 정렬·이진 탐색·Top K·BFS를 하나의 Java 프로그램으로 연결합니다.
• 일반·빈·중복·경계값 테스트와 확장 체크리스트를 완성합니다.

◇3. 핵심 개념

최종 프로그램은 ArrayList에 원본 순서를 저장하고 HashMap에 플레이어별 기록 참조를 색인합니다. 점수 기준 복사본을 정렬한 뒤 이진 탐색으로 동점 구간의 첫 위치를 찾습니다. 상위 K는 최소 힙, 스테이지 도달 순서는 인접 리스트와 BFS를 사용합니다. 하나의 구조가 모든 연산에 최적일 필요는 없으며, 중복 저장과 색인의 일관성을 책임 있게 관리해야 합니다.

요구	선택	입력 크기와 연산 기준
입력 순서 보존·전체 조회	ArrayList<GameRecord>	끝 추가와 순차 조회가 많고 중간 삽입은 필요하지 않습니다.
플레이어별 반복 조회	HashMap<String, List<GameRecord>>	기록 n개를 매번 훑지 않고 플레이어 키로 접근합니다.
전체 점수 순위	복사본 + Comparator 정렬	모든 n개 순서가 필요하므로 O(n log n) 정렬을 사용합니다.
특정 점수 검색	정렬 목록 + lower bound	같은 정렬 목록에 질의가 반복될 때 O(log n) 탐색이 의미가 있습니다.
상위 K개	K 크기 PriorityQueue	K가 n보다 훨씬 작을 때 전체 정렬을 피합니다.
스테이지 도달 탐색	인접 리스트 + BFS	희소 그래프의 V개 정점과 E개 간선만 저장하고 방문합니다.

검증 데이터는 세 묶음으로 나눕니다.

데이터	포함하는 값	확인할 동작
일반	서로 다른 플레이어와 여러 점수·스테이지	정렬, 색인, Top K, BFS
빈 데이터	기록과 간선이 없음	빈 결과를 예외 없이 반환
중복·경계값	같은 플레이어 두 기록, 점수 0과 Integer.MAX_VALUE	중복 보존, overflow 없는 비교, 경계 검색

✎4. 단계별 실습

시작 전 상태

• 1~23강 예제의 배열·HashMap·정렬·이진 탐색·PriorityQueue·그래프 코드를 다시 열 수 있어야 합니다.
• java -version과 javac -version이 같은 LTS JDK를 가리켜야 합니다.
• C:\dev\game-ranking-algorithms\src에 기존 실습 파일이 있다면 Git 상태를 확인하고 최종 파일을 별도로 만듭니다.
• 완성 코드를 한 번에 붙여 넣기 전에 아래 수직 조각마다 컴파일·출력·복잡도를 확인합니다.

가장 작은 수직 조각과 구현 순서

최종 결과를 한 번에 만들지 말고 “입력 한 개가 저장되고 질문 한 개에 답한다”부터 확장합니다.

순서	구현 조각	이 단계의 통과 기준
1	GameRecord와 입력 검증	정상 기록 1개가 생성되고 빈 ID·음수 값은 거부됩니다.
2	records와 byPlayer를 함께 갱신	P1 기록 2개를 추가했을 때 원본 2개·색인 2개가 같습니다.
3	점수 복사본 정렬과 lower bound	원본 순서는 그대로이고 1500의 첫 오름차순 인덱스는 2입니다.
4	K 크기 최소 힙	K=2일 때 1500점 두 기록만 남습니다.
5	인접 리스트와 BFS	1에서 시작해 1·2·3·4를 한 번씩 방문합니다.
6	일반·빈·경계 테스트 통합	마지막 통과 문구까지 AssertionError 없이 출력됩니다.

한 단계가 실패한 상태에서 다음 자료구조를 추가하지 않습니다. 예를 들어 색인이 틀린 상태에서 정렬까지 붙이면 어느 구조가 결과를 망쳤는지 찾기 어려워집니다.

1. 예제 파일 작성

실행 환경: 코드 편집기

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

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

대상 파일: src/GameRankingApp.java

src/GameRankingApp.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

public class GameRankingApp {
    record GameRecord(String playerId, int score, int playSeconds, int stage) {
        GameRecord {
            if (playerId == null || playerId.isBlank()) throw new IllegalArgumentException("빈 플레이어 ID");
            if (score < 0 || playSeconds < 0 || stage < 1) throw new IllegalArgumentException("음수 또는 잘못된 스테이지");
        }
    }

    static final class RankingSystem {
        private static final Comparator<GameRecord> SCORE_ASC =
                Comparator.comparingInt(GameRecord::score).thenComparing(GameRecord::playerId);
        private final List<GameRecord> records = new ArrayList<>();
        private final Map<String, List<GameRecord>> byPlayer = new HashMap<>();
        private final Map<Integer, Set<Integer>> stages = new HashMap<>();

        void add(GameRecord record) {
            records.add(record);
            byPlayer.computeIfAbsent(record.playerId(), key -> new ArrayList<>()).add(record);
            stages.computeIfAbsent(record.stage(), key -> new HashSet<>());
        }
        List<GameRecord> findByPlayer(String playerId) {
            return List.copyOf(byPlayer.getOrDefault(playerId, List.of()));
        }
        List<GameRecord> sortedByScore() {
            List<GameRecord> sorted = new ArrayList<>(records);
            sorted.sort(SCORE_ASC.reversed());
            return sorted;
        }
        int firstIndexOfScore(int target) {
            List<GameRecord> sorted = new ArrayList<>(records);
            sorted.sort(SCORE_ASC);
            int low = 0, high = sorted.size();
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (sorted.get(mid).score() < target) low = mid + 1;
                else high = mid;
            }
            return low < sorted.size() && sorted.get(low).score() == target ? low : -1;
        }
        List<GameRecord> topK(int k) {
            if (k <= 0) return List.of();
            PriorityQueue<GameRecord> heap = new PriorityQueue<>(SCORE_ASC);
            for (GameRecord record : records) {
                heap.offer(record);
                if (heap.size() > k) heap.poll();
            }
            List<GameRecord> result = new ArrayList<>(heap);
            result.sort(SCORE_ASC.reversed());
            return result;
        }
        void connectStages(int a, int b) {
            stages.computeIfAbsent(a, key -> new HashSet<>()).add(b);
            stages.computeIfAbsent(b, key -> new HashSet<>()).add(a);
        }
        List<Integer> reachableFrom(int start) {
            List<Integer> order = new ArrayList<>();
            Queue<Integer> queue = new ArrayDeque<>();
            Set<Integer> visited = new HashSet<>();
            queue.offer(start); visited.add(start);
            while (!queue.isEmpty()) {
                int current = queue.poll(); order.add(current);
                for (int next : stages.getOrDefault(current, Set.of())) {
                    if (visited.add(next)) queue.offer(next);
                }
            }
            return order;
        }
        int size() { return records.size(); }
    }

    static RankingSystem normalData() {
        RankingSystem system = new RankingSystem();
        system.add(new GameRecord("P1", 1200, 80, 1));
        system.add(new GameRecord("P2", 1500, 95, 2));
        system.add(new GameRecord("P1", 1500, 70, 3));
        system.add(new GameRecord("P3", 600, 110, 2));
        system.connectStages(1, 2); system.connectStages(2, 3); system.connectStages(3, 4);
        return system;
    }

    static void require(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        RankingSystem normal = normalData();
        require(normal.size() == 4, "일반 데이터 개수");
        require(normal.findByPlayer("P1").size() == 2, "중복 플레이어 색인");
        require(normal.firstIndexOfScore(1500) >= 0, "경계 점수 이진 탐색");
        require(normal.topK(2).size() == 2, "상위 K");
        require(normal.reachableFrom(1).containsAll(List.of(1, 2, 3, 4)), "BFS 연결");

        RankingSystem empty = new RankingSystem();
        require(empty.sortedByScore().isEmpty() && empty.topK(3).isEmpty(), "빈 데이터");

        RankingSystem boundary = new RankingSystem();
        boundary.add(new GameRecord("DUP", 0, 0, 1));
        boundary.add(new GameRecord("DUP", Integer.MAX_VALUE, 1, 1));
        require(boundary.findByPlayer("DUP").size() == 2, "중복·경계값");

        System.out.println("점수 정렬: " + normal.sortedByScore());
        System.out.println("P1 기록: " + normal.findByPlayer("P1"));
        System.out.println("상위 2개: " + normal.topK(2));
        System.out.println("스테이지 BFS: " + normal.reachableFrom(1));
        System.out.println("일반·빈·중복·경계값 테스트 통과");
    }
}

핵심 코드와 알고리즘 해설

1. GameRecord의 compact constructor는 잘못된 값이 자료구조에 들어가기 전에 막습니다. 이후 알고리즘이 “점수는 0 이상, 스테이지는 1 이상”이라는 전제를 믿을 수 있습니다.
2. add 하나가 원본 List와 플레이어 Map을 함께 갱신합니다. 호출자가 두 구조를 따로 수정하지 못하게 해 색인 불일치를 줄입니다.
3. List.copyOf는 플레이어 색인의 내부 List를 직접 노출하지 않습니다. 반환받은 코드가 clear()로 원본 색인을 훼손할 수 없습니다.
4. sortedByScore는 복사본만 정렬하므로 입력 순서가 저장된 records는 변하지 않습니다.
5. lower bound 반복문은 [0, low)는 target보다 작고 [high, size)는 target 이상이라는 범위를 줄입니다. 반복이 끝난 low가 실제 target인지 마지막에 확인해야 없는 점수를 잘못 찾지 않습니다.
6. Top K 최소 힙은 지금까지 본 후보 중 가장 작은 값을 루트에 둡니다. 크기가 K를 넘을 때 루트를 제거하면 큰 K개만 남습니다.
7. BFS는 정점을 Queue에 넣는 순간 visited에 추가합니다. 꺼낼 때 추가하면 여러 이웃이 같은 정점을 중복으로 Queue에 넣을 수 있습니다.

손으로 검산하는 일반 데이터

질문	손으로 계산한 결과	코드에서 볼 위치
원본 순서	P1 1200 → P2 1500 → P1 1500 → P3 600	records
P1 색인	1200점, 1500점 두 기록	findByPlayer("P1")
내림차순 정렬	P2 1500, P1 1500, P1 1200, P3 600	sortedByScore()
오름차순 1500 첫 위치	600, 1200 다음인 인덱스 2	firstIndexOfScore(1500)
Top 2	P2 1500, P1 1500	topK(2)
BFS 방문 집합	1, 2, 3, 4	reachableFrom(1)

동점 정렬은 SCORE_ASC.reversed() 때문에 점수뿐 아니라 보조 기준 playerId도 역순이 됩니다. 요구사항이 “동점은 ID 오름차순”이라면 Comparator를 점수 내림차순과 ID 오름차순으로 명시적으로 조합해야 합니다. BFS 인접 Set의 순회 순서는 계약상 고정되지 않으므로 현재 테스트는 정확한 배열 순서가 아니라 네 정점 포함 여부를 검증합니다.

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

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

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

대상: src/GameRankingApp.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\GameRankingApp.java
java -cp .\out GameRankingApp

예상 결과: record의 기본 문자열에는 필드 이름이 포함됩니다. BFS 순서는 Set 구현에 따라 달라질 수 있지만 1·2·3·4가 한 번씩 포함되고 마지막 통과 문구가 나와야 합니다.

점수 정렬: [GameRecord[playerId=P2, score=1500, ...], GameRecord[playerId=P1, score=1500, ...], ...]
P1 기록: [GameRecord[playerId=P1, score=1200, ...], GameRecord[playerId=P1, score=1500, ...]]
상위 2개: [GameRecord[playerId=P2, score=1500, ...], GameRecord[playerId=P1, score=1500, ...]]
스테이지 BFS: [1, 2, 3, 4]
일반·빈·중복·경계값 테스트 통과

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

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

추가는 List와 HashMap에 평균 O(1), 플레이어 조회는 평균 O(1)+결과 r개 복사 O(r)입니다. 점수 정렬은 O(n log n), 정렬 후 이진 탐색은 O(log n)이지만 현재 메서드는 매번 복사·정렬하므로 전체 O(n log n)입니다. Top K는 O(n log k), BFS는 O(V+E)입니다. 반복 점수 질의가 많다면 정렬 색인을 한 번 만들고 추가 시 무효화하는 설계로 개선할 수 있습니다.

기능	최선	평균	최악	추가 공간
기록 추가	O(1)	amortized O(1)	O(n), 배열 확장·해시 충돌 가능	색인 포함 O(n)
플레이어 조회	O(1)	O(1) + O(r) 복사	O(n) + O(r)	반환값 O(r)
점수 정렬	O(n log n) 기준	O(n log n)	O(n log n) 비교 정렬 기준	복사본 O(n)
현재 점수 검색 메서드 전체	O(n log n)	O(n log n)	O(n log n)	정렬 복사본 O(n)
상위 K	O(n log k) 기준	O(n log k)	O(n log k)	O(k)
BFS	O(1), 시작점만 존재	O(V + E)	O(V + E)	O(V)

여기서 r은 해당 플레이어의 기록 수, V는 스테이지 수, E는 연결 수입니다. 표준 컬렉션의 해시 평균 성능과 구현 정렬 세부를 절대적인 모든 환경의 보장으로 확대하지 않습니다.

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

!자주 하는 실수

• 실수: 여러 색인을 갱신하다 일부만 변경하기 해결: add 한 메서드가 원본과 색인을 함께 갱신하도록 캡슐화합니다.
• 실수: 이진 탐색만 O(log n)이라고 보고 매번 정렬하는 비용을 빼기 해결: 호출 전체는 현재 O(n log n)임을 명시합니다.
• 실수: PriorityQueue나 Set의 순회 순서에 의존하기 해결: 출력 순서는 별도 정렬하고 BFS 순서가 필요하면 이웃 구조를 정렬된 컬렉션으로 바꿉니다.

✎7. 직접 실습

따라 하기: 기준 결과 고정

위 코드를 직접 작성해 컴파일하고 여섯 손 검산 결과와 실제 출력을 대조합니다. 테스트 통과 문구만 보는 대신 정렬 순서·P1 개수·Top K·BFS 집합을 각각 확인합니다.

값과 실패 바꿔 보기

1. firstIndexOfScore(1499)가 -1인지 확인합니다.
2. topK(0), topK(10)을 호출해 각각 빈 결과와 전체 4개 결과가 나오는 정책을 기록합니다.
3. new GameRecord("", 100, 10, 1)과 음수 점수·0번 스테이지를 각각 생성해 IllegalArgumentException 메시지를 확인합니다.
4. 스테이지 연결 3-4를 제거해 1에서 4에 도달하지 못하는 실패 그래프를 만듭니다.

직접 확장: 반복 점수 검색 캐시

점수 오름차순 복사본을 필드로 캐시하고 add가 호출되면 무효화하세요. 첫 검색은 O(n log n), 변경 없는 다음 검색은 O(log n)이 되도록 합니다. 캐시를 갱신하지 않아 오래된 결과가 나오는 테스트를 먼저 작성하면 무효화 이유가 분명해집니다.

날짜 필드를 추가해 기간 필터 뒤 Top K를 구하는 확장은 캐시 검증을 끝낸 다음 진행합니다. 간선에 이동 비용이 생기면 BFS가 아닌 가중치 최단 경로가 필요하다는 한계도 문서에 남깁니다.

스스로 확인

✎직접 실습

• C:\dev\game-ranking-algorithms에서 javac -Xlint:all -d out src\GameRankingApp.java가 성공합니다.
• java -cp out GameRankingApp가 다섯 결과와 테스트 통과 문구를 출력합니다.
• 원본 List와 플레이어 색인의 기록 수가 모든 추가 뒤 일치합니다.
• 빈 ID, 음수 점수·시간, 1보다 작은 스테이지가 거부됩니다.
• 빈 데이터, K=0, K>n, 없는 점수, 끊긴 그래프를 검증했습니다.
• 캐시 사용 전후 firstIndexOfScore 전체 복잡도를 구분했습니다.

막혔을 때

증상	가능한 원인	확인과 해결
P1 원본은 2개인데 색인은 1개	byPlayer.put으로 List를 덮어씀	computeIfAbsent(...).add(record)가 add 안에서 항상 실행되는지 봅니다.
lower bound가 없는 점수의 삽입 위치를 반환	마지막 동등성 검사 누락	low < size와 score == target을 모두 확인합니다.
Top K가 낮은 점수를 남김	최대 힙을 만들거나 제거 조건이 반대	K 크기 최소 힙에서 가장 작은 후보를 제거합니다.
BFS가 같은 정점을 반복 방문	visited 추가 시점이 늦음	Queue에 넣는 순간 visited.add(next) 결과를 검사합니다.
캐시 뒤 새 기록이 검색되지 않음	add에서 정렬 캐시 무효화 누락	모든 변경 진입점을 add 하나로 유지하고 캐시를 null 또는 dirty로 표시합니다.

실습 기록에는 입력 크기, 예상·실제 결과, 시간·공간 복잡도와 JDK 버전을 남깁니다. 실제 사용자 ID 대신 P1, P2 같은 가상 데이터를 사용합니다.

?8. 이해 점검 질문 3개

?이해 점검

1. 원본 List와 플레이어 Map을 함께 유지하는 이유는 무엇인가요?
2. 같은 점수를 1만 번 검색해야 할 때 현재 firstIndexOfScore를 그대로 호출하면 어떤 비용이 반복되며 어떤 캐시 전략이 필요한가요?
3. 플레이어 기록이 백만 개이고 K가 10일 때 전체 정렬보다 최소 힙을 선택하는 이유와, 스테이지 연결 탐색에는 Queue를 선택하는 이유는 각각 무엇인가요?

■9. 핵심 요약

■핵심 요약

최종 프로그램은 요구별로 ArrayList, HashMap, 정렬·이진 탐색, 최소 힙, 인접 리스트·BFS를 조합합니다. 각 구조의 갱신 책임과 전체 호출 복잡도, 경계 테스트를 함께 관리해야 합니다.