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. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: 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("일반·빈·중복·경계값 테스트 통과");
    }
}

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

예상 결과: 점수 정렬, P1 기록, 상위 2개, 스테이지 BFS 결과 뒤에 일반·빈·중복·경계값 테스트 통과가 출력됩니다.

실행 시간은 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. 직접 실습

✎직접 실습

1. 날짜 필드를 추가하고 기간 필터 뒤 상위 K를 계산합니다.
2. 점수 정렬 색인을 캐시하고 add 시 무효화합니다.
3. 잘못된 빈 ID·음수 값 예외 테스트를 추가하고 메시지를 확인합니다.

완료 체크리스트

• C:\dev\game-ranking-algorithms에서 javac -Xlint:all -d out src\GameRankingApp.java가 성공합니다.
• java -cp out GameRankingApp가 다섯 결과와 테스트 통과 문구를 출력합니다.
• 빈 ID, 음수 점수·시간, 1보다 작은 스테이지가 IllegalArgumentException으로 거부됩니다.
• 빈 데이터와 K가 0인 입력이 빈 결과를 반환합니다.
• 확장 아이디어 1: 날짜별 기록을 추가해 기간 랭킹을 계산합니다.
• 확장 아이디어 2: 정렬 색인을 캐시해 반복 이진 탐색의 전체 비용을 줄입니다.
• 확장 아이디어 3: 간선에 이동 비용을 추가하고 가중치 최단 경로 알고리즘을 학습합니다.

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

?8. 이해 점검 질문 3개

?이해 점검

1. 원본 List와 플레이어 Map을 함께 유지하는 이유는 무엇인가요?
2. 현재 firstIndexOfScore 호출 전체가 O(n log n)인 이유는 무엇인가요?
3. Top K와 BFS가 각각 선택한 자료구조는 무엇인가요?

■9. 핵심 요약

■핵심 요약

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