11. 달리기 경주 ★ (dictionary 자료형 사용해 index 찾기)

유형 : 구현

하하...

 

<오답 풀이>

def solution(players, callings):
    answer = players
    for call in callings:
        idx = players.index(call)
        temp = players.pop(idx)
        temp = players.pop(idx-1)
        players.insert(idx-1, call)
        players.insert(idx, temp)
    return answer

 

이렇게 단순히 list로 풀 경우... index, pop, insert 함수들은 O(n) 시간 복잡도이기 떄문에 시간 초과가 난다. 

따라서 빠르게 key를 찾을 수 있는 dict를 사용해야 한다. 

 

<정답 풀이>

def solution(players, callings):
    playdict = dict([[players[i], i] for i in range(len(players))])
    answer = players
    for call in callings:
        idx = playdict[call]
        answer[idx], answer[idx-1] = answer[idx-1], answer[idx]
        
        playdict[call] = idx-1
        playdict[answer[idx]] = idx
    return answer

 

dict를 사용해 index를 더 빠르게 찾을 수 있다.