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

def solution(players, callings):
    
    # {'mumu': 0, 'soe': 1, 'poe': 2, 'kai': 3, 'mine': 4}
    player_dict = {player:rank for rank,player in enumerate(players)}
    # {0: 'mumu', 1: 'soe', 2: 'poe', 3: 'kai', 4: 'mine'}
    rank_dict = {rank:player for rank,player in enumerate(players)}
    
    for call in callings:
        call_index = player_dict[call]
        prev_index = call_index -1
        
        player_dict[rank_dict[call_index]], player_dict[rank_dict[prev_index]] = prev_index, call_index
        rank_dict[call_index], rank_dict[prev_index] = rank_dict[prev_index], rank_dict[call_index]
        
    return list(rank_dict.values())

이번 문제는 단순하게 callings 배열의 원소들을 가지고 자리를 바꿔주는 방식으로 구현하거나 사전 자료형을 사용하지 않고 풀이하면 시간초과가 발생하게 된다.

 

가장 중요한 핵심은 리스트 자료형에서 index를 찾는 index() 메서드는 O(n)의 시간복잡도를 가지므로, 입력 값의 크기가 큰 경우에는 시간초과가 발생한다. 따라서 선수 이름과 등수를 key-value 형태로 저장하는 사전 자료형을 선언한 뒤, O(1)의 시간복잡도로 index를 구해야 문제를 해결할 수 있다는 점이다.