[알고리즘/Python] 해시(Hash) vs 정렬(Sort) 성능 비교 : O(N) 최적화 경험 (feat. 완주하지 못한 선수)

1. 문제

• 문제: 프로그래머스 - 완주하지 못한 선수
• 유형: 해시 (Hash)
• 난이도: Level 1
• 목표: 마라톤 참여자 중 완주하지 못한 단 한 명을 찾아내야 한다. (동명이인 존재 가능)

---

2. 첫 번째 접근 : 정렬(Sorting) 활용

처음에는 가장 직관적인 방법으로 접근했다. 두 리스트를 모두 정렬한 뒤, 순서대로 비교하다가 달라지는 부분이 있다면 그 사람이 완주하지 못한 사람이다.

def solution(participant, completion):
    # 1. 두 리스트를 정렬 (O(N log N))
    participant.sort()
    completion.sort()

    # 2. zip으로 묶어서 순서대로 비교
    for p, c in zip(participant, completion):
        if p != c:
            return p
            
    # 3. 끝까지 다 돌았다면 마지막 남은 사람이 범인
    return participant[-1]

• 코드 설명: zip을 활용해 깔끔하게 구현했다.
• 시간 복잡도: sort() 함수를 사용했기 때문에 O(N log N)이 소요된다.
• 아쉬운 점: 효율성 테스트는 통과하지만, 입력값(N)이 커질수록 정렬 비용이 부담스러울 수 있다.

---

3. 두 번째 접근 : 해시(Hash) 활용한 최적화 (O(N))

시간 복잡도를 개선하기 위해 파이썬의 collections.Counter를 사용했다. 정렬할 필요 없이 데이터를 한 번만 훑으면 되므로 속도가 훨씬 빠르다.

import collections

def solution(participant, completion):
    # 1. 참가자와 완주자의 이름 개수를 센다 (Hash Map 생성)
    p_count = collections.Counter(participant)
    c_count = collections.Counter(completion)
    
    # 2. 차집합 연산 (객체끼리 빼기 가능)
    result = p_count - c_count
    
    # 3. 남은 하나의 key를 반환
    return list(result.keys())[0]

• 코드 설명: Counter 객체 간의 빼기 연산(-)을 지원하는 파이썬의 강력한 기능을 활용했다.
• 시간 복잡도: 리스트를 한 번 순회하여 딕셔너리를 만드므로 O(N)이다.

---

4. 성능 비교 및 회고 (Sort vs Hash)

비교 항목	정렬 (Sorting) 방식	해시 (Hash) 방식
시간 복잡도	O(N log N)	O(N)
공간 복잡도	O(1) (구현에 따라 다름)	O(N) (추가 메모리 사용)
특징	로직이 직관적임	대용량 데이터 처리에 유리함

[배운 점]

단순히 문제를 푸는 것(Correctness)을 넘어, 시간 복잡도(Performance)를 고려하는 것이 중요하다는 것을 배웠다.

• Sort 방식은 N=100만 기준 약 2,000만 번 연산이 필요하지만,
• Hash 방식은 약 100만 번 연산으로 끝난다. (약 20배 차이)

현업에서 대용량 데이터를 다룰 때는 메모리를 조금 더 쓰더라도(Time-Space Trade-off), 속도를 획기적으로 줄일 수 있는 Hash(O(N)) 방식이 더 적합한 접근임을 깨달았다.