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

🧩 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/178871

 

1️⃣ 풀이방법1 - 시간초과

def solution(players, callings):
    for calling in callings:
        i = players.index(calling)
        if i != 0:
            players[i], players[i - 1] = players[i - 1], players[i]
    return players

list.index()의 시간 복잡도는 O(players의 길이)이다.

for문을 callings 만큼 반복하므로 최악의 경우 시간 복잡도는 O(players의 길이 * callings의 길이)이다.

 

 

 

2️⃣ 풀이방법2 - 정답

딕셔너리를 이용해 찾고, swap 하는 방법으로 접근해보았다.

딕셔너리의 검색, 교환 연산은 시간복잡도가 O(1)이기 때문에 시간 복잡도는 O(callings의 길이)이다. 

위에서 index()를 사용한 방법보다 시간복잡도도 줄었다!

def solution(players, callings):
    player_dict = {p:i for i,p in enumerate(players)}
    index_dict = {i:p for i,p in enumerate(players)}
    
    
    for calling in callings:
        current_index = player_dict[calling] # 현재 인덱스 
        front = index_dict[current_index - 1] # 추월한 선수 이름 
        
        # swap
        player_dict[calling], player_dict[front] = player_dict[front], player_dict[calling]
        index_dict[current_index], index_dict[current_index - 1] = index_dict[current_index - 1], index_dict[current_index]
        
        
    return list(index_dict.values())

성공💖