프로그래머스 | Python | 단순구현, Hash | 달리기 경주 (Lv.1)

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

프로그래머스

 

1. 문제 풀이 접근

이 문제는 해설진이 부른 선수(callings)가 추월하면서 players 리스트의 순서를 실시간으로 변경해야 합니다.

즉, 선수의 현재 등수를 빠르게 찾고, 변경하는 것이 핵심입니다.

• 선수들의 순위를 저장할 때 list.index()를 사용하면 시간복잡도가 O(N)으로 비효율적입니다.
• 해설진이 callings를 최대 1,000,000번 부를 수 있기 때문에, O(N) 탐색을 반복하면 최악의 경우 O(N * M) = 50,000 * 1,000,000 = 50,000,000,000(500억 번 연산)이 되어 시간 초과가 발생합니다.
• 따라서, 딕셔너리(해시맵)를 사용해 선수의 등수를 빠르게 조회하고 갱신하는 것이 중요합니다.

---

2. 해결 방법 (시간복잡도 O(M))

✅ 핵심 아이디어

• players 리스트를 기반으로 선수 이름을 key, 등수를 value로 하는 딕셔너리(rank_map)를 생성
• callings을 순회하며 다음 연산을 수행
  1. 불린 선수의 등수를 rank_map에서 가져옴
  2. 앞 선수와 위치를 바꿈
  3. players 리스트를 업데이트
  4. rank_map을 업데이트 (등수를 빠르게 갱신하기 위해)

이 방식은 players 리스트를 O(1)로 조회하고, swap 연산을 수행하여 callings의 길이(M)만큼만 반복하면 되므로 O(M) 연산으로 해결할 수 있습니다.

---

3. Python 코드

def solution(players, callings):
    # 선수들의 등수를 저장하는 딕셔너리 (key: 선수 이름, value: 현재 등수)
    rank_map = {player: i for i, player in enumerate(players)}

    # callings의 선수들을 순회하며 등수를 변경
    for calling in callings:
        current_rank = rank_map[calling]  # 불린 선수의 현재 등수
        if current_rank == 0:
            continue  # 1등은 호출되지 않으므로 따로 처리할 필요 없음

        # 바로 앞 선수와 자리 변경
        front_player = players[current_rank - 1]
        
        players[current_rank - 1], players[current_rank] = players[current_rank], players[current_rank - 1]

        # 등수 정보 갱신
        rank_map[calling] -= 1
        rank_map[front_player] += 1

    return players

---

4. 시간복잡도 분석

✅ players 리스트 초기화

• rank_map = {player: i for i, player in enumerate(players)} → O(N)

✅ callings 순회하면서 등수 변경 (M번 반복)

• rank_map[calling] → O(1)
• players에서 swap 연산 → O(1)
• rank_map 갱신 → O(1)
• 총 O(M) 연산

따라서 최종 시간복잡도는 O(N) + O(M) ≈ O(M)으로 매우 효율적입니다.

---

5. 코드 해설

📌 변수별 의미 및 흐름 설명

1️⃣ rank_map (선수 등수를 저장하는 딕셔너리)

rank_map = {player: i for i, player in enumerate(players)}

• players 리스트의 선수 이름을 키(key)로, 현재 등수를 값(value)으로 저장
• 예를 들어, players = ["mumu", "soe", "poe", "kai", "mine"] 일 때즉, 각 선수의 현재 등수를 빠르게 조회할 수 있도록 설정.
• rank_map = { "mumu": 0, "soe": 1, "poe": 2, "kai": 3, "mine": 4 }

---

2️⃣ current_rank (불린 선수의 현재 등수 찾기)

current_rank = rank_map[calling]

• calling(불린 선수)이 현재 몇 등인지 rank_map에서 가져옴.
• 예를 들어, callings = ["kai"]이고 "kai"가 불렸다면즉, "kai"는 현재 4등(0-based index로 3).
• current_rank = rank_map["kai"] # 3

---

3️⃣ front_player (불린 선수의 앞에 있는 선수 찾기)

front_player의 역할

front_player = players[current_rank - 1]

• players[current_rank - 1]을 먼저 저장하여 자리 변경 후에도 원래 값을 기억할 수 있도록 함
• 만약 이 변수를 사용하지 않고 players[current_rank - 1]을 바로 참조하면, 값이 바뀐 후의 상태를 잘못 참조할 위험이 있음
• 불린 선수(calling)의 앞 순위에 있는 선수를 찾음.
• "kai"가 불렸다면, "kai"의 current_rank = 3이므로즉, "kai"의 앞에는 "poe"가 있음.
• front_player = players[2] # "poe"

---

4️⃣ 선수 위치 변경

players[current_rank - 1], players[current_rank] = players[current_rank], players[current_rank - 1]

• "kai"(4등)와 "poe"(3등)의 위치를 서로 바꿈.
• 변경 전
• players = ["mumu", "soe", "poe", "kai", "mine"]
• 변경 후"kai"가 "poe"를 추월하여 3등이 됨.
• players = ["mumu", "soe", "kai", "poe", "mine"]

---

5️⃣ 선수 등수 정보 갱신

rank_map[calling] -= 1
rank_map[front_player] += 1

• "kai"가 3등으로 올라갔으므로 등수를 1 감소
• "poe"가 4등으로 내려갔으므로 등수를 +1 증가
• 변경 후 rank_map
• rank_map = { "mumu": 0, "soe": 1, "kai": 2, # 3등 → 2등으로 올라감 "poe": 3, # 2등 → 3등으로 내려감 "mine": 4 }

---

📌 최종 정리

1. rank_map 딕셔너리를 사용해 각 선수의 현재 등수를 O(1)로 찾음
2. 불린 선수(calling)의 등수를 rank_map에서 조회하여 current_rank를 얻음
3. 불린 선수의 앞 순위 선수(front_player)를 찾아 위치를 바꿈
4. 위치 변경 후, rank_map의 등수 정보를 갱신
5. 모든 호출(callings)을 반복하여 최종 players 리스트를 반환

이 방식은 리스트에서 .index()를 사용해 등수를 찾는 O(NM) 비효율적 접근법 대신 O(N + M)으로 최적화된 방법이다.

---

6. 핵심 포인트 정리

• 리스트 탐색을 O(1)로 하기 위해 딕셔너리(해시맵)를 사용
• 순위 정보를 빠르게 갱신하기 위해 players 리스트와 rank_map을 동기화
• 시간복잡도를 O(N + M)으로 최적화하여 빠르게 해결 (브루트포스 방식(O(NM))을 피함)

📌 "해시맵을 사용한 등수 갱신 최적화"가 핵심 포인트입니다.