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

문제

처음 배열로 선수 리스트가 주어지고, 한 선수가 앞 선수를 추월할 때마다 해설진들에게 호명되며 최종적으로 결승에 들어온 순서대로 선수 리스트를 반환하면 되는 문제

 

풀이 과정

1. 첫 번째 풀이

def switch(players, index):
    save = players[index] #호명 된 선수
    players[index] = players[index-1]
    players[index-1] = save
    
    return players   

def solution(players, callings):
    
    for calling in callings:
        players = switch(players, players.index(calling))

    return players

 

for 문을 이용하여 호명된 선수를 바꿔주는 방식으로 해결하려 하였으나

해당 풀이 방법은 결과는 맞지만 시간초과로 실패하였다.

 

2. 두 번째 풀이

def recursive_function(players, callings):
    if len(callings) == 0:
        return players
    
    index = players.index(callings[0])
    save = players[index]
    players[index] = players[index-1]
    players[index-1] = save
    del callings[0]
    
    return recursive_function(players, callings)

def solution(players, callings):
    return recursive_function(players, callings)

 

for 문 대신 재귀함수를 이용

그러나 해당 풀이 방법 또한 결과는 맞지만 런타임 에러로 실패하였다.

 

아무 생각 없이 풀다가 생각해보니 for문과 재귀 함수 둘 다 시간복잡도가 O(n) 이었다.

 

다만 for문은 시간 초과, 재귀 함수는 메모리(스택)를 사용하다보니 런타임 에러가 발생 했던 것이다.

 

그렇다면 다른 부분에서 시간 초과가 발생했다는 말인데..

 

찾아보니 리스트 대신 딕셔너리를 사용하여 해결하면 된다고 한다.

 

이 또한 확인해보니

 

시간복잡도

리스트 : O(N)
해시테이블 : O(1) , 최악의 경우 - O(N)

 

다음과 같이 해시 테이블을 이용하는 딕셔너리가 속도면에서 더 빠르다는 것을 알 수 있었다.

 

최종 코드

def solution(players, callings):
    player_rank = {player : rank for rank, player in enumerate(players)}
    rank_player = {rank : player for rank, player in enumerate(players)}
    
    for calling in callings:
        calling_player_rank = player_rank[calling] #호명 된 선수 랭킹
        front_player_rank = calling_player_rank-1 # 호명 된 선수 앞 선수 랭킹
        front_player = rank_player[front_player_rank]  # 앞 선수 이름
        
        #딕셔너리 변경
        rank_player[calling_player_rank] = front_player 
        rank_player[front_player_rank] = calling
        
        player_rank[calling] = front_player_rank
        player_rank[front_player] = calling_player_rank
        
    
    return list(rank_player.values())

 

딕셔너리를 하나로 사용해보려 했지만 그랬을 경우 리스트를 사용함으로써 다시 시간초과가 나와 딕셔너리 두 개를 사용하여 해결해 주었다.