[Lv.1 / 프로그래머스 / 파이썬] 달리기 경주

 

 

 

프로그래머스

 

 

 

 

 

풀이

 

 

최소한의 비용으로 players 의 위치를 탐색해 순위를 바꿔야 하는 문제이다.

단순히 callings 에 있는 이름들을 players 리스트를 순회하며 찾는다면 50,000 * 1,000,000 만큼의 비용이 발생할 것이다.

따라서 callings 에 있는 이름을 playres 에서 O(1) 만에 탐색할 수 있는 딕셔너리와 같은 HashMap 을 사용해야 한다.

 

def solution(players, callings):
    rank = dict()
    for i in range(len(players)):
        rank[players[i]] = i
    
    for name in callings:
        idx = rank[name]
        # 인덱스 변경
        rank[players[idx-1]], rank[name] = rank[name], rank[players[idx-1]]
        
        # 실제 위치 변경
        players[idx], players[idx-1], = players[idx-1], players[idx]
        
    return players