[코딩 테스트, 더 이상 미룰 수 없다] 프로그래머스lv1 - 달리기 경주(Python으로 양방향 매핑 문제)

 

이번 달리기 경주 문제를 풀면서 가장 크게 배운 것은 양방향 매핑(Bidirectional Mapping) 이라는 구현 패턴이다.

처음에는 선수의 이름과 순위를 Dictionary 하나로만 관리하려고 했다.

rate[player] = index

이렇게 하면

kai -> 3

처럼 이름 → 순위는 바로 찾을 수 있다.

하지만 추월이 발생하면 문제가 생긴다.

예를 들어

0 mumu
1 soe
2 poe
3 kai

에서 kai가 추월하면

먼저 kai의 순위는 쉽게 찾을 수 있다.

rank = rate["kai"]

하지만 그 앞에 있는 사람이 누구인지는 어떻게 찾을까?

Dictionary만으로는

3 → kai

와 같은 순위 → 이름을 찾을 수 없다.

결국 앞 사람을 찾기 위해 리스트를 다시 탐색해야 하고, 시간도 오래 걸린다.

---

양방향 매핑

이 문제에서는 두 개의 자료구조를 동시에 관리하는 것이 핵심이다.

1. 이름 → 순위

name_to_rank = {}

for rank, name in enumerate(players):
    name_to_rank[name] = rank

mumu -> 0
soe -> 1
poe -> 2
kai -> 3

---

2. 순위 → 이름

사실 별도의 Dictionary를 만들 필요도 없다.

players 리스트 자체가

0 -> mumu
1 -> soe
2 -> poe
3 -> kai

를 이미 표현하고 있다.

즉,

• Dictionary : 이름 → 순위
• List : 순위 → 이름

두 자료구조가 서로를 보완하는 구조가 된다.

---

추월은 Swap이다.

추월이 일어나면 순위가 다시 정렬되는 것이 아니다.

두 사람의 위치만 서로 바뀐다.

예를 들어

0 mumu
1 soe
2 poe
3 kai

에서

kai가 추월하면

0 mumu
1 soe
2 kai
3 poe

가 된다.

이때 Python에서는

players[rank], players[rank - 1] = players[rank - 1], players[rank]

처럼 튜플 스왑을 사용하면 두 값을 간단하게 교환할 수 있다.

그리고 Dictionary도 함께 수정한다.

name_to_rank[calling] -= 1
name_to_rank[front] += 1

이렇게 하면 List와 Dictionary가 항상 같은 정보를 유지하게 된다.

---

구현 문제에서 자주 나오는 패턴

이번 문제를 통해 알게 된 구현 패턴은 다음과 같다.

객체 → 위치  : Dictionary

위치 → 객체  : List

이 구조는 순위뿐 아니라

• 좌석 배치
• 플레이어 위치
• 카드 위치
• 캐릭터 이동
• 배열에서 위치가 자주 바뀌는 문제

에서도 반복해서 사용할 수 있는 패턴이다.

---

이번 문제 복습 포인트

• 하나의 자료구조만으로 해결하려 하지 말고, 양방향으로 조회가 필요한지 먼저 생각하기
• List는 인덱스 → 값을 빠르게 찾을 수 있다.
• Dictionary는 값 → 인덱스를 빠르게 찾을 수 있다.
• 위치 변경은 전체를 다시 정렬하는 것이 아니라 Swap으로 해결하는 경우가 많다.
• 구현 문제에서는 자료구조를 하나 더 두는 것이 오히려 코드가 더 단순해지는 경우가 많다.

이번 문제를 통해 구현 문제는 알고리즘보다 어떤 자료구조를 선택하느냐가 성능과 코드의 복잡도를 결정한다는 점을 다시 느꼈다.