Programmers_LV1_달리기경주

def solution(players, callings):
    dict_p = {player : int(idx) for idx, player in enumerate(players)} 
    # O(n)
    
    for i in callings: # O(n)
        rank = dict_p[i] # 이름 불린 선수의 랭크 O(1)
        front_p = players[rank-1] # 앞 선수 이름 O(1)
        hold_p = players[rank] # 이름 불린 선수 이름 O(1)
        rank_f = dict_p[front_p] # 앞 선수 랭크 O(1)
        
        # 기존 자료구조 수정
        # 딕셔너리(플레이어 이름 기준)
        dict_p[i] -= 1 #O(1)
        dict_p[front_p] += 1 #O(1)
        
        # 리스트(랭크 기준)
        players[rank_f] = hold_p #O(1)
        players[rank] = front_p #O(1)
        
        # 시간복잡도 O(n+k)
    return players

자료구조 이해가 필요한 작업, 리스트는 index를 기준으로 O(1)만에 조회가 가능하지만 value를 기준으로는 O(n)의 조회가 필요하다. 또한 index는 0부터의 정수로 결정되어있다. list의 index를 선수 이름으로 할 수 없으므로 key를 기준으로 O(1)만에 조회가 가능한 dictionary를 만든다.

그렇기에 메모리가 두 배로 증가하지만, 속도를 위해서 dictionary로 키값이 선수이름이고 랭크가 value인 딕셔너리를 하나 더 만드는 것.

for문을 통해 callings의 원소를 하나씩 가져와서 불리운 선수와 그 앞 랭크의 선수의 이름과 rank를 모두 확보한다. 그리고 key와 index에 해당하는 값을 이용해서 두 자료구조를 수정한다.

만약 list만을 이용하거나 dictionary만을 이용한다면 시간초과 문제가 발생할 것이다.