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

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

프로그래머스

 

 

---

아이디어

그냥 불린 이름 idx 찾아서 앞에 있는 거랑 swap 해주면 된다고 생각해서 코드를 아래처럼 짰는데 특정 케이스에서 시간 초과가 나왔다.

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

 

왜그런지 찾아보다가 index 찾는 함수의 시간 복잡도가 O(n)이라서 전체 코드는 O(n^2)이 나와 시간 초과가 나온 것 같다.

 

딕셔너리로 풀면 시간 복잡도를 줄일 수 있다고 한다.

그래서 처음에 {player : 등수}로 딕셔너리 만들어주고 코드를 짰다.

 

---

코드

def solution(players, callings):
    answer = []
    dict = {player: i for i, player in enumerate(players)}
    
    for name in callings:
        idx = dict[name] # 호출된 선수 인덱스
        dict[name] -= 1 # 역전했으므로 -1
        dict[players[idx-1]] += 1 # 호출 선수 앞에 있는 선수는 역전 당했으므로 +1
        players[idx], players[idx-1] = players[idx-1], players[idx] # swap
    
        
    return players