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

https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

 

풀이

def solution(players, callings):
    for name in callings:
        i = players.index(name)
        players[i] = players[i-1]
        players[i-1] = name 
    
    return players

테스트케이스 9-13번까지 시간 초과가 났다.

 

name의 등수를 찾을 때 index를 써서 난 오류이다.

index는 내부적으로 앞에서부터 하나씩 순차 탐색한다. 

최악의 경우 1,000,000 초가 걸리기 때문에 시간 초과가 남

 

그러나 dict는 해시 테이블 구조를 사용해 해시캆으로 메모리 주소를 계산하므로 바로 접근한다

(거의 항상 한 번에 찾는다)

 

따라서 key: 이름, value: 등수로 dict를 만들어놓고 등수를 변경해주면 시간 초과없이 잘 작동한다

 

전체 코드

def solution(players, callings):
    
    name_rank_dict = {}
    for i in range(len(players)):
        name_rank_dict[players[i]] = i # 이름: 등수 
    
    
    for name in callings:
        i = name_rank_dict[name]
        prev = players[i-1]
        
        players[i] = players[i-1]
        players[i-1] = name 
        
        name_rank_dict[name] -= 1 
        name_rank_dict[prev] += 1 
        
    return players