[Python] 프로그래머스 Lv1 - 달리기 경주

🔗 문제 링크

프로그래머스

📂 분류

구현, 자료구조

💡 풀이

제한사항을 고려하지 않고 list의 index 와 swap을 이용해서 문제를 해결했으나 시간초과가 발생했다.
시간초과 이유는 최대 1,000,000 * 50,000 = 500억 이므로 O(N^2)의 시간복잡도를 가지는 알고리즘은 사용할 수 없었다.

player의 순위를 dictionary에 저장하여 swap을 사용했다.

💻 코드

def solution(players, callings):
    rank =  {key : i for i, key in enumerate(players)}

    for calling in callings:
        index = rank[calling]
        rank[calling] -= 1 # 추월한 선수
        rank[players[index - 1]] += 1 # 추월당한 선수
        players[index - 1], players[index] = players[index], players[index - 1]

    return players