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

레벨1이지만 정답률 40%...문제

 

맨 처음에 rank = [] 를 만들어서 call마다 rank 값을 조정하는 코드를 짰는데 시간초과가 났다.

 

 

그 다음 리스트의 원소끼리 swap하도록 간결하게 수정했다.

채점에서 5개 테스트 시간복잡도에 걸렸다...

 

list swap

def solution(players, callings):
    answer = []
    
    for call in callings:
        called_index = players.index(call)
        
        players[called_index-1], players[called_index] = players[called_index], players[called_index-1]
    
    return players

 

 

제한사항의 배열 길이가 최대 50000이기 때문에 인덱스로 서치하면 시간복잡도에 걸리게 된다.

 

 

이를 해결하기 위해 빠르게 서치할 수 있는 key-value방법으로 바꾼다.

 

 

 

딕셔너리 방법

def solution(players, callings):

    players_rank = {string: i for i, string in enumerate(players)}
    
    for call in callings:
        cur_rank = players_rank[call]
        
        players_rank[call] -= 1
        players_rank[players[cur_rank-1]] += 1
        
        players[cur_rank-1], players[cur_rank] = call, players[cur_rank-1]
        
   
    return players

딕셔너리에 현재 등수를 value값으로 저장한 후 for루프를 돌면서 rank가 바뀔때마다 딕셔너리의 순위를 바꿔준다.

그리고 바뀐 순위대로 player 순서도 바꾸어주면 끝.