[프로그래머스] 달리기 경주 (Python)

문제 링크

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

프로그래머스

소스 코드

def solution(players, callings):
    player_dict = {players[x]:x for x in range(len(players))}
    rank_dict = {x:players[x] for x in range(len(players))}
    
    for name in callings:
        player_dict[name] -= 1 # 뒤에 있던 애 순위 높이기
        prev_rank = player_dict[name] # 앞 순위 기록하기
        rank_dict[prev_rank],rank_dict[prev_rank+1] = rank_dict[prev_rank+1],rank_dict[prev_rank] # 랭킹 교체
        prev_name = rank_dict[prev_rank+1] # 앞에 있던 애 이름 뽑기
        player_dict[prev_name] += 1 # 앞에 있던 애 순위 낮추기

    return list(rank_dict.values())

해설

• 시간 복잡도를 고려하여 해시로 풀이

해시 

원래는 엄청 쉬워 보이네 하고 간단하게 구현하니 시간 초과가 발생했습니다.

그러고 나서야 문제 조건을 보니까 players는 최대 50,000, callings의 길이는 최대 1,000,000인 걸 알 수 있었습니다.

(이런 조건들을 먼저 살펴야 유형 파악에 도움이 되는데 오랜만이라 감을 잃었나 봅니다 😅)

그래서 일반적인 리스트에 인덱스로 접근하게 되면 리스트 길이에 비례하여 시간이 걸리기 때문에 최대 50,000 x 1,000,000 = ??? 가 됩니다.

 

따라서 O(N)의 시간 복잡도를 갖는 리스트의 인덱스 대신에 O(1)의 시간 복잡도를 갖는 해시(딕셔너리)로 접근하는 것이죠!

다른 분의 풀이를 보면 딕셔너리 하나만 가지고도 풀이가 가능하긴 한데, 

당장 직관적으로 떠오르는 것은 딕셔너리 두 개를 사용하는 것 같습니다.

 

{이름 : 순위}, {순위 : 이름} 두 개의 딕셔너리를 준비합니다.

조건에서 주어지는 것은 사람의 이름이라서 이를 토대로 순위를 검색해야 하는데, 다음 사람은 순위를 기준으로 검색해야 하기 때문이죠.

 

첫 번째 예를 생각해보면 kai가 불리면서 poe와 순서를 바꿔줘야 합니다.

하지만 {이름 : 순위} 딕셔너리만 있다면 poe가 몇 번째 위치하고 있는지 구하기가 어렵겠죠.

그래서 {순위 : 이름} 딕셔너리도 생성하여 순위와 이름을 동시에 기록하고 교환하는 방식을 취해줍니다.

 

결과적으로는 리스트 callings 길이에 상수로 비례한 시간복잡도를 가지며 문제를 풀이할 수 있게 됩니다!