[프로그래머스] 달리기 경주 Python 풀이(시간초과 해결, dictionary 사용)

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

프로그래머스

 

예제 입력:

players = ["mumu", "soe", "poe", "kai", "mine"]

callings = ["kai", "kai", "mine", "mine"]

 

예제 출력:

result = ["mumu", "kai", "mine", "soe", "poe"]

 

풀이

해설진은 선수들이 자기 바로 앞의 선수를 추월할때 추월한 선수의 이름을 부른다. 결기가 끝난 후 선수들의 이름이 불려진 순서를 1등부터 순서대로 배열에 담아 return하는 문제이다.

간단하다고 생각하고 풀었더니 또 시간초과에서 터졌다^^...

 

처음 작성한 코드:

def solution(players, callings):
    
    for call in callings:
        
        a = players.index(call) #이름이 불리는 선수의 players의 위치
        players[a], players[a-1] = players[a-1], players[a]
        
    return players

 

처음 작성한 코드에서는 callings 배열에서 이름이 불린 선수를 찾기 위해 .index()를 사용했다. 시간 초과된 후 생각해 보니 이렇게 하면 시간 복잡도가 O(n)이므로, 선수가 많고 경기가 길어질수록 효율성이 떨어질 수 있겠다는 생각이 들었다.

즉, 인덱스를 빠르게 찾을 수 있는 자료구조를 사용해야 하고 dictionary가 그 해답이다. 이름이 불린 선수의 위치를 빠르게 찾고, 해당 선수와 그 앞의 선수의 위치를 바꾸면 된다(이 로직은 똑같다).

dictionary를 사용하면 각 호출마다 시간 복잡도가 O(1)이 되기 때문에 훨씬 효율적으로 해결된다.

 

정답 코드:

def solution(players, callings):
    player_dict = {player: idx for idx, player in enumerate(players)}
    
    for call in callings:
        idx = player_dict[call]
        
        players[idx], players[idx-1] = players[idx-1], players[idx]
        
        player_dict[players[idx]] = idx
        player_dict[players[idx-1]] = idx-1
    
    return players

해결했다! 조금 더 효율성에 유의하며 푸는 습관을 길러야겠다.