23강. 문제 풀이 설계법: 입력·제약·예외·복잡도 점검

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

예제를 보고 바로 코딩하면 데이터가 비었거나 중복되고 입력이 커졌을 때 실패하는 해법을 만들기 쉽습니다.

✓2. 학습 목표

✓이 강의를 마치면

• 문제의 입력·출력·제약을 분리합니다.
• 연산 빈도에 맞춰 List·Map·Heap을 선택합니다.
• 정확성 테스트와 복잡도 검토 순서를 만듭니다.

◇3. 핵심 개념

풀이 전에 ① 입력의 의미와 최대 크기, ② 출력과 동점 규칙, ③ 반복되는 연산, ④ 빈 값·중복·최솟값·최댓값, ⑤ 허용 시간·메모리를 적습니다. 그 뒤 단순한 기준 풀이를 세우고 필요한 부분만 개선합니다. 복잡도는 자료구조 구축, 질의, 출력 정렬을 모두 더해 계산합니다. 성능 측정값은 환경·JVM 워밍업·입력 분포에 따라 달라지므로 복잡도 분석을 대체하지 않습니다.

✎4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

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

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

대상 파일: src/RankingProblemDesign.java

src/RankingProblemDesign.java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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

    static List<GameRecord> bestPerPlayer(List<GameRecord> records) {
        Map<String, GameRecord> best = new HashMap<>();
        for (GameRecord record : records) {
            if (record.playerId() == null || record.playerId().isBlank() || record.score() < 0) continue;
            best.merge(record.playerId(), record,
                    (a, b) -> a.score() >= b.score() ? a : b);
        }
        List<GameRecord> ranking = new ArrayList<>(best.values());
        ranking.sort(Comparator.comparingInt(GameRecord::score).reversed()
                .thenComparing(GameRecord::playerId));
        return ranking;
    }

    public static void main(String[] args) {
        List<GameRecord> input = List.of(new GameRecord("P1", 900),
                new GameRecord("P2", 1200), new GameRecord("P1", 1400),
                new GameRecord("", 9999));
        System.out.println(bestPerPlayer(input));
        System.out.println(bestPerPlayer(List.of()));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

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

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

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

예상 결과: 유효한 플레이어별 최고 기록이 점수순으로 출력되고 빈 입력은 빈 목록을 반환합니다.

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

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

n개 기록을 Map으로 집계하는 평균 시간은 O(n), 서로 다른 플레이어 p명을 정렬하는 시간은 O(p log p), 공간은 O(p)입니다. ID가 빈 기록과 음수 점수 정책을 코드에서 명시합니다. 요구가 상위 K뿐이면 전체 정렬 대신 힙을 선택할 수 있습니다.

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

!자주 하는 실수

• 실수: 샘플 입력만 통과하면 완료라고 판단하기 해결: 빈 값·중복·경계값 테스트를 먼저 목록화합니다.
• 실수: 각 단계 복잡도를 따로만 적기 해결: 전처리+질의+정렬+출력의 전체 비용을 합칩니다.
• 실수: 측정 한 번으로 알고리즘 우열을 확정하기 해결: 동일 조건 반복 측정과 복잡도 근거를 함께 사용합니다.

✎7. 직접 실습

✎직접 실습

1. 입력 최대 1천과 1천만일 때 가능한 풀이를 각각 제안합니다.
2. 상위 10명만 필요하도록 PriorityQueue 해법을 설계합니다.
3. 정확성 체크리스트와 복잡도 표를 코드 작성 전에 만듭니다.

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

?8. 이해 점검 질문 3개

?이해 점검

1. 코딩 전에 확인할 네 가지 문제 정보는 무엇인가요?
2. 플레이어 수 p가 기록 수 n보다 작을 때 집계 후 정렬 비용은 무엇인가요?
3. 벤치마크가 Big-O 분석을 대체하지 못하는 이유는 무엇인가요?

■9. 핵심 요약

■핵심 요약

좋은 풀이는 문제를 명확히 정의하고 기준 해법, 경계 테스트, 전체 복잡도 순서로 설계합니다. 측정은 환경 의존 증거이며 자료구조 선택 근거와 함께 사용합니다.