[Python] Hash Map과 List를 활용한 O(N) 효율적 위치 추적 구현 ([달리기 경주])

🚀 Introduction: 왜 우리는 더 빠른 검색에 집착하는가?

오늘 다룬 문제는 단순한 '순서 바꾸기'처럼 보이지만, 그 이면에는 데이터 검색 속도와 성능 최적화라는 알고리즘의 핵심 과제가 숨어 있습니다. 대규모 서비스 환경에서 특정 사용자의 상태를 업데이트할 때마다 전체 명단을 처음부터 끝까지 뒤져야 한다면 어떻게 될까요? 데이터가 100만 개라면, 단 한 번의 업데이트를 위해 100만 번의 연산이 필요해집니다.

오늘은 리스트의 물리적 순서를 유지하면서도, 검색 성능을 $O(1)$로 끌어올리는 해시 테이블(Hash Table) 기반의 딕셔너리 활용법을 정리해 보았습니다.

---

🔍 The Challenge (Deep Dive): 리스트 순회, 무엇이 병목(Bottleneck)인가?

처음 문제를 접했을 때 가장 직관적인 접근은 for문을 돌려 타겟을 찾는 방식이었습니다. 하지만 여기서 두 가지 기술적 병목을 마주했습니다.

1. 데이터 유실의 위험: 단순 대입(=)은 추월을 구현하는 것이 아니라 기존 데이터를 '덮어쓰기' 때문에 선수의 정보가 유실됩니다. 즉, 데이터의 정합성을 지키기 위한 Swap(교환) 로직이 필수적이었습니다.
2. 선형 탐색(Linear Search)의 한계: answer[i] == c를 찾기 위해 매번 리스트 전체를 순회하는 이중 반복문 구조는 시간 복잡도 $O(N \times M)$을 유발합니다. $N$(선수 수)이 5만, $M$(호출 수)이 10만일 경우 연산 횟수는 최대 50억 번에 달하며, 이는 반드시 시간 초과(Time Limit Exceeded)로 이어집니다.

---

💡 Technical Insight: 자료구조의 트레이드 오프(Trade-off)

이 병목을 해결하기 위해 파이썬의 dict 자료구조를 도입했습니다. 파이썬의 딕셔너리는 내부적으로 해시 테이블로 구현되어 있어, Key를 통해 Value를 찾는 과정이 평균적으로 $O(1)$에 수행됩니다.

내가 지금 손에 든 정보(선수 이름)로 무엇(인덱스)을 찾고 싶은지를 고민하여 {Name: Index} 형태의 '역색인' 구조를 설계했습니다.

📊 자료구조 비교: List vs Dict (Hash Map)

자료구조	탐색 방식	시간 복잡도	비고
List	순차 탐색 (Linear)	$O(N)$	데이터가 많아질수록 탐색 시간이 정비례하여 증가함
Dict (Hash)	해시 탐색 (Hash)	$O(1)$	해시 테이블을 사용하여 데이터 양과 관계없이 즉시 찾음

단, 딕셔너리만으로는 최종 정답인 '선수들의 순서'를 즉각 반환하기 어렵기 때문에, 순서를 담당하는 리스트와 검색을 담당하는 딕셔너리를 동시에 업데이트하는 '이중 장부' 전략을 선택했습니다.

---

✅ The Solution & Code

최종 구현 코드

def solution(players, callings):
    # 1. '이름: 등수' 형태의 해시 맵(rank_dict) 초기화 (O(N))
    # 이름표(Key)를 주면 등수(Value)를 광속으로 찾아주는 '거꾸로 사전'
    rank_dict = {player: i for i, player in enumerate(players)}
    
    for c in callings:
        # 2. 호명된 선수의 현재 인덱스를 해시 맵에서 O(1)로 조회
        i = rank_dict[c]
        
        # 3. Swap을 위해 앞 순서 선수(Target) 식별
        # 자리를 바꾼 뒤에도 장부를 수정해야 하므로 이름을 미리 메모해둠(front_player)
        front_player = players[i - 1]
        
        # 4. List 데이터 업데이트: 실제 물리적 위치 교체 (O(1))
        # 파이썬의 튜플 언패킹을 활용한 우아한 Swap
        players[i - 1], players[i] = players[i], players[i - 1]
        
        # 5. Dict 데이터 업데이트: 해시 맵 내 인덱스 정보 동기화
        # 내 인덱스는 줄이고, 밀려난 앞 선수의 인덱스는 늘려줌
        rank_dict[c] -= 1
        rank_dict[front_player] += 1
        
    return players

---

📈 Summary

• 시간 복잡도: 딕셔너리 초기화($O(N)$) + 호출 순회($O(M)$) = $O(N + M)$. 최악의 상황에서도 약 15만 번의 연산으로 해결 가능합니다.
• 공간 복잡도: 리스트 외에 별도의 딕셔너리를 사용하므로 $O(N)$의 추가 공간이 필요하지만, 성능 최적화를 위한 합리적인 비용(Trade-off)입니다.