프로그래머스 Level 1 | 달리기 경주 | Python

https://school.programmers.co.kr/learn/courses/30/lessons/178871

---

문제 파악

달리기 경주를 하는 player들의 이름이 담긴 배열 players 와
해설진들이 달리기 선수들이 추월할 때 부르는 이름이 담긴 배열 callings 가 주어진다.

이 때 경기 결과 등수 배열 result 를 return 하는 문제이다.

players 배열에 mumu, soe, poe, kai, mine 이 있고,
callings 배열에 kai, kai, mine, mine 이 있다면
kai와 mine의 인덱스가 2개씩 앞으로 당겨져서, result는
mumu, kai, mine, soe, poe 가 된다.

---

풀이 아이디어

어떻게 풀 수 있을까
kai가 불리면 어떤 일이 일어날까?
kai의 인덱스가 -1 이 되고, kai의 인덱스 -1 번째 있던 자리의 인덱스는 +1 이된다.

결국 callings 배열에 따라 선수들의 순서가 계속 바뀌는 것을 구현해야 한다.
단순히 players 배열에서 인덱스를 찾아 swap 하는 방식으로 접근하면 시간복잡도가 너무 커진다.
왜냐하면 선수 수가 최대 50,000명, callings가 최대 1,000,000번이 될 수 있기 때문이다.

그래서 이름 → 현재 등수(인덱스), 등수 → 이름 두 가지를 동시에 관리하는 해시맵(dict)을 만들어야 한다.

---

로직 정리

1. 초기화

   • name_to_rank: 선수 이름을 key, 현재 인덱스를 value로 저장
   • rank_to_name: 현재 인덱스를 key, 선수 이름을 value로 저장

2. 호명 처리

   • 어떤 이름 x가 불리면 현재 순위를 가져온다 → idx = name_to_rank[x]
   • idx - 1 위치에 있는 선수와 자리를 바꾼다 (swap)
   • 두 해시맵 모두 업데이트

3. 최종 결과

   • 모든 callings 처리가 끝나면 rank_to_name 기준으로 결과를 만들어 return

---

코드

def solution(players, callings):
    # 1) 초기화
    name_to_rank = {name: i for i, name in enumerate(players)}
    rank_to_name = {i: name for i, name in enumerate(players)}

    # 2) 호명 처리
    for name in callings:
        cur_rank = name_to_rank[name]        # 현재 등수
        front_rank = cur_rank - 1            # 앞사람 등수

        if front_rank < 0:                   # 이미 1등이면 무시
            continue

        # 앞사람 이름 찾기
        front_name = rank_to_name[front_rank]

        # swap (rank_to_name 갱신)
        rank_to_name[front_rank], rank_to_name[cur_rank] = (
            rank_to_name[cur_rank],
            rank_to_name[front_rank],
        )

        # swap (name_to_rank 갱신)
        name_to_rank[name] = front_rank
        name_to_rank[front_name] = cur_rank

    # 3) 결과 반환
    result = [rank_to_name[i] for i in range(len(players))]
    return result