1 문제 정보

제목: 완주하지 못한 선수
링크: https://school.programmers.co.kr/learn/courses/30/lessons/42576
난이도: 1
유형: Hash
풀이 시간: 10분

2 문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

2.1 제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.

2.2 입출력 예

participant	completion	return
[“leo”, “kiki”, “eden”]	[“eden”, “kiki”]	“leo”
[“marina”, “josipa”, “nikola”, “vinko”, “filipa”]	[“josipa”, “filipa”, “marina”, “nikola”]	“vinko”
[“mislav”, “stanko”, “mislav”, “ana”]	[“stanko”, “ana”, “mislav”]	“mislav”

2.3 입출력 예 설명

2.3.1 예제 #1

“leo”는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

2.3.2 예제 #2

“vinko”는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

2.3.3 예제 #3

“mislav”는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

※ 공지 - 2023년 01월 25일 테스트케이스가 추가되었습니다.

3 문제 해설

3.1 문제 핵심 이해

이 문제의 핵심은 두 개의 배열에서 빠진 요소 하나를 찾는 것

참가자 배열: participant (n명)
완주자 배열: completion (n-1명)
목표: 완주하지 못한 1명 찾기

3.2 중요한 조건들

동명이인 존재 가능: 단순히 이름만 비교하면 안 되고, 개수까지 고려해야 한다.
대용량 데이터: 최대 100,000명까지 가능하므로 효율적인 알고리즘이 필요하다.
정확히 1명 차이: completion 길이 = participant 길이 - 1

3.3 해결 방법별 분석

3.3.1 해시맵(Dictionary) 방법 (권장)

시간복잡도: O(n) + O(n) + O(n) = O(n) 공간복잡도: O(n) (최악의 경우 모든 참가자가 서로 다른 이름)

'''
핵심 아이디어
  - 해설: 완주하지 못한 선수는 참가했지만 완주 명단에서 차감되지 않은 유일한 사람이므로, 카운팅 차집합으로 정확히 찾을 수 있음 
  - 전략: 참가자 카운트 - 완주자 카운트 = 미완주자의 차집합 원리를 해시맵으로 구현 
알고리즘 동작
  - 참가자 딕셔너리 생성: 각 참가자 이름별 개수를 해시맵에 저장
  - 완주자 카운트 차감: 완주자 리스트를 순회하며 해당 이름의 카운트를 1씩 차감
  - 미완주자 탐색: 카운트 값이 0보다 큰 이름을 찾아 반환
왜 효율적인가?
  - 해시맵의 O(1) 접근 시간을 활용하여 전체 O(n) 시간에 동명이인까지 정확히 처리할 수 있음
'''
def solution(participant, completion):
    participant_dict = {} # 최대 n개의 서로 다른 이름 저장 → O(n) 공간
    
    # 1단계: 참가자 카운트 - O(n)
    for name in participant:  # n번 반복
        participant_dict[name] = participant_dict.get(name, 0) + 1
        # 잘못된 방법 - participant_dict[name] = participant_dict[name] + 1
          # → KeyError: 'leo' (처음 등장하는 이름은 키가 없음)
        # dict.get(key, default_value): 값을 가져오는 역할
          # name이라는 키가 딕셔너리에 있으면 → 그 값을 반환
          # name이라는 키가 딕셔너리에 없으면 → 0을 반환 (default 값)
        # + 1 → 참가자 개수 증가 (동명이인 방지)
          # 두 번째 "leo" (만약 동명이인이 있다면) → 1 + 1 = 2
        # dict.get() = O(1), dict 할당 = O(1)
        # 예시: ["mislav", "stanko", "mislav", "ana"] → {"mislav": 2, "stanko": 1, "ana": 1}
          # # 1. name = "mislav" (첫 번째)
          # participant_dict.get("mislav", 0) + 1
          # # → 0 + 1 = 1
          # participant_dict["mislav"] = 1
          # # 현재 상태: {"mislav": 1}
# 
          # # 2. name = "stanko"
          # participant_dict.get("stanko", 0) + 1  
          # # → 0 + 1 = 1
          # participant_dict["stanko"] = 1
          # # 현재 상태: {"mislav": 1, "stanko": 1}
# 
          # # 3. name = "mislav" (두 번째, 동명이인!)
          # participant_dict.get("mislav", 0) + 1
          # # → 1 + 1 = 2  (이미 "mislav"가 있어서 1을 반환)
          # participant_dict["mislav"] = 2
          # # 현재 상태: {"mislav": 2, "stanko": 1}
# 
          # # 4. name = "ana"
          # participant_dict.get("ana", 0) + 1
          # # → 0 + 1 = 1
          # participant_dict["ana"] = 1
          # # 최종 상태: {"mislav": 2, "stanko": 1, "ana": 1}
    
    # 2단계: 완주자 차감 - O(n-1) = O(n)
    for name in completion:  # n-1번 반복
        participant_dict[name] -= 1
        # dict 접근 및 수정 = O(1)
    
    # 3단계: 결과 찾기 - O(n)
    for name, count in participant_dict.items():  # 최대 n번 반복
        if count == 1:
            return name

동작 원리: - 참가자 이름별 개수를 카운트 - 완주자 이름별로 개수를 차감 - 남은 개수가 1인 사람이 미완주자

3.3.2 정렬 방법

시간복잡도: O(n log n) + O(n log n) + O(n) = O(n log n)

분할 정복(Divide and Conquer) 원리
- 분할: 배열을 절반씩 나누기 → log n 단계 → n개의 요소를 계속 반으로 나누면서 1개가 남을 때까지의 분할 횟수가 log n
- n개의 요소를 계속 반으로 나누면서 1개가 남을 때까지의 분할 횟수가 log n
- n → n/2 → n/4 → n/8 → … → n/2^k → … → 1 - n/2^k = 1 → 2^k = n → k = log₂n → O(log n)
- 예시: 8개 요소 정렬 - [8, 3, 1, 7, 0, 10, 2, 5]
  - 1단계: [8,3,1,7] | [0,10,2,5] ← 8 → 4, 4
  - 2단계: [8,3|1,7] | [0,10|2,5] ← 4 → 2, 2
  - 3단계: [8|3|1|7] | [0|10|2|5] ← 2 → 1, 1
- 총 단계 수: log₂(8) = 3단계 = log n
- 각 단계마다: 8개 요소 처리 = n개
- 반으로 나누는 것만으로도 문제 크기를 지수적으로 줄일 수 있어서 O(n) 보다 O(log n)이 더 효율적
- 정복: 각 단계에서 모든 요소를 비교/병합 → n 개 요소
- 결과: log n 단계 × n개 처리 = O(n log n)

공간복잡도: O(1) (입력 배열 자체를 정렬) - O(1) = 상수 시간 (Constant Time)

입력 크기에 상관없이 항상 일정한 시간이 걸리는 연산
즉, 추가 메모리를 거의 사용하지 않는다는 뜻 - 모두 O(1) 연산들

arr[0]           # 배열 인덱스 접근 = O(1)
dict[key]        # 해시맵 접근 = O(1)
x = 5            # 변수 할당
if x > 0:        # 단순 비교
    return x     # 반환

def solution(participant, completion):
    participant.sort() # 시간: O(n log n), 공간: O(1)
    completion.sort() # 시간: O(n log n), 공간: O(1)
    
    # 순서대로 비교하다가 다른 부분 발견 → 시간: O(n), 공간: O(1)
    for i in range(len(completion)):  # n-1번 반복
        if participant[i] != completion[i]: # O(1)
            return participant[i]
    
    # 모두 같다면 마지막 사람이 미완주자
    return participant[-1] # O(1)

따라서, 정렬 방법의 시간복잡도는 O(n log n)이고, 공간복잡도는 O(1)

시간복잡도: O(n log n) + O(n log n) + O(n) = O(n log n)
공간복잡도: O(1) + O(1) + O(1) = O(1)
메모리 vs 속도 트레이드오프
결론: 대부분 상황에서는 해시맵이 좋지만, 메모리가 부족한 환경에서는 정렬 방법을 고려할 수 있다

방법	속도	메모리	상황
해시맵	빠름 O(n)	많이 씀 O(n)	일반적으로 권장
정렬	보통 O(n log n)	적게 씀 O(1)	메모리 제약이 있을 때

3.3.3 최적 해답 (해시맵 사용)

def solution(participant, completion):
    # 방법 1: Counter 사용 (가장 간단)
    from collections import Counter
    
    participant_counter = Counter(participant) # O(n)
    completion_counter = Counter(completion) # O(n)
    
    # 차집합으로 미완주자 찾기
    result = participant_counter - completion_counter # O(n)
    return list(result.keys())[0] # O(1)

3.3.4 한 줄 해답 (고급)

def solution(participant, completion):
    from collections import Counter
    return list((Counter(participant) - Counter(completion)).keys())[0]

3.3.5 브루트 포스 방법 (비권장)

시간복잡도: O(n²)
공간복잡도: O(1)

def solution(participant, completion):
    for p in participant:
        if p not in completion:
            return p
        else:
            completion.remove(p)  # 동명이인 처리

3.4 복잡도 비교표

방법	시간복잡도	공간복잡도	특징
해시맵	O(n)	O(n)	최적 성능, 가독성 좋음
Counter	O(n)	O(n)	가장 간결, 최적 성능
정렬	O(n log n)	O(1)	메모리 효율적
브루트포스	O(n²)	O(1)	비효율적, 비권장

3.5 왜 해시맵이 최적인가?

해시 테이블의 특성: 삽입, 조회, 수정이 모두 O(1)
선형 탐색: 각 배열을 한 번씩만 순회 → O(n)
공간-시간 트레이드오프: 메모리를 조금 더 사용해서 시간을 크게 단축
시간 효율성: O(n) - 각 배열을 한 번씩만 순회
동명이인 처리: 이름별 개수를 정확히 관리
구현 단순성: 직관적이고 이해하기 쉬운 로직
확장성: 미완주자가 여러 명이어도 쉽게 확장 가능

3.6 핵심 포인트

Hash 자료구조의 특성 활용: O(1) 삽입/조회로 효율성 극대화
카운팅 기법: 단순 존재 여부가 아닌 개수 비교로 동명이인 문제 해결
차집합 개념: 전체에서 일부를 빼는 방식으로 누락된 요소 찾기

대용량 데이터(최대 100,000명)에서는 O(n)과 O(n²)의 차이가 매우 크기 때문에 해시맵 방식이 필수적이다

3.7 예제별 동작 과정

3.7.1 예제 1: `["leo", "kiki", "eden"]`, `["eden", "kiki"]`

해시맵 방법: 1. participant_dict = {“leo”: 1, “kiki”: 1, “eden”: 1} 2. “eden” 차감 → {“leo”: 1, “kiki”: 1, “eden”: 0} 3. “kiki” 차감 → {“leo”: 1, “kiki”: 0, “eden”: 0} 4. count가 1인 “leo” 반환

3.7.2 예제 3: `["mislav", "stanko", "mislav", "ana"]`, `["stanko", "ana", "mislav"]`

해시맵 방법: 1. participant_dict = {“mislav”: 2, “stanko”: 1, “ana”: 1} 2. 완주자들 차감 후 → {“mislav”: 1, “stanko”: 0, “ana”: 0} 3. count가 1인 “mislav” 반환

4 해시맵 기초

해시맵(해시테이블): 컴퓨터 과학 이론에서 사용하는 표준 학술 용어
Python 딕셔너리 = 해시맵(해시테이블) = 해시 기반 키-값 저장소
딕셔너리의 Key → 해시함수 → 인덱스 → 메모리 위치 → Value 할당

4.1 딕셔너리의 내부 구현

Python의 dict는 실제로 해시테이블(Hash Table)로 구현되어 있음 - 즉, 해시맵과 동일한 자료구조 - my_dict = {"key": "value"} - 내부적으로는 해시테이블이 동작 - 1. “key”를 해시함수에 통과 → hash(“key”) = 12345 - 2. 12345 % 배열크기 = 인덱스 계산 - 3. 해당 인덱스에 (“key”, “value”) 저장

4.2 언어별 용어 차이

언어	이름	실제로는
Python	dict	Hash Table
Java	HashMap	Hash Table
C++	unordered_map	Hash Table
JavaScript	Object, Map	Hash Table
C#	Dictionary	Hash Table

4.3 왜 “해시맵”이라고 부르는가?

4.3.1 해시 함수 사용

# 내부 동작 과정
key = "leo"
hash_value = hash("leo")  # 예: 2578946130
index = hash_value % 8    # 배열 크기가 8이면 → 인덱스 2
# dict_array[2] 위치에 ("leo", 1) 저장

4.3.2 키-값 매핑(Mapping)

# 키를 값으로 "매핑(mapping)"
"leo" → 1
"kiki" → 1  
"eden" → 1

4.4 해시맵의 핵심 특성

4.4.1 O(1) 평균 시간복잡도

# 모두 O(1) 평균 시간
dict["key"]           # 조회
dict["key"] = value   # 삽입  
dict["key"] += 1      # 수정

4.4.2 해시 충돌 처리

# 서로 다른 키가 같은 해시값을 가질 때
hash("leo") % 8 = 2
hash("ana") % 8 = 2  # 충돌!

# Python은 Open Addressing으로 해결
# Open Addressing: 다음 빈 슬롯을 찾아 저장