[Programmers] 달리기 경주

문제 링크

Lv1

def solution(players, callings):
    l = 0
    name = ''
    dic1 = {}
    dic2 = dict()
    
    for i in range(len(players)):
        dic1[i] = players[i]
        dic2[players[i]] = i
        
    
    for i in callings :
        l = dic2[i] # i 위치가져오기
        name = dic1[l-1]
        dic1[l-1], dic1[l] = dic1[l],dic1[l-1]
        dic2[i],dic2[name] = dic2[name], dic2[i]
        

    answer = list(dic1.values())
    return answer

lv1이길래 쉽게 swap 사용해서 풀었더니 시간초과가 나왔다.
최대길이가 callings가 1,000,000 players가 50,000 이기 때문에 시간 복잡도를 중요하게 생각하고 풀어야했다.
index함수를 for문이랑 함께 썼더니 시간복잡도가 O(NM)으로 엄청 커져버렸다.
힌트들을 보니 딕셔너리 사용을 해야한다고 해서 어찌저찌 풀어봄
시간복잡도 다시 공부해야지...