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

Set과 중복 제거: 고유 플레이어·아이템 관리

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

09강. Set과 중복 제거: 고유 플레이어·아이템 관리

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

같은 플레이어가 여러 기록에 등장해도 고유 플레이어 수는 한 번만 세어야 하며, 중복 보상 코드는 거부해야 합니다.

2. 학습 목표

3. 핵심 개념

Set은 동등한 원소를 하나만 보관합니다. HashSet은 해시 기반이라 add·contains가 평균 O(1)이지만 출력 순서를 보장하지 않습니다. 삽입 순서가 필요하면 LinkedHashSet, 정렬 순서가 필요하면 TreeSet처럼 요구에 맞는 구현을 검토합니다. 중복 제거 후 순서가 필요하다면 무조건 HashSet 하나로 끝내지 않습니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

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

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

대상 파일: src/UniquePlayers.java

src/UniquePlayers.java
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class UniquePlayers {
    public static void main(String[] args) {
        List<String> playerIds = List.of("P1", "P2", "P1", "P3", "P2");
        Set<String> unique = new HashSet<>();
        for (String id : playerIds) {
            if (!unique.add(id)) System.out.println("중복 발견: " + id);
        }
        System.out.println("고유 플레이어 수: " + unique.size());
        System.out.println("P3 참가: " + unique.contains("P3"));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

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

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

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

예상 결과: P1과 P2의 중복 안내, 고유 플레이어 수 3, P3 참가 true가 출력됩니다. Set 출력 순서는 사용하지 않습니다.

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

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

add는 원소가 새로 들어가면 true, 이미 동등한 원소가 있으면 false입니다. n개 입력을 처리하는 평균 시간은 O(n), 최악은 충돌 상황에 따라 커질 수 있으며 고유 원소 u개에 O(u) 공간을 사용합니다.

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

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ