[Python][CodingTest] 달리기 경주

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

프로그래머스

뭐야 생각보다 쉬운데 ? 하고 

1차 시간 초과

def solution(players, callings):
    for call_player in callings:
        # ex) kai 일때, kai 의 idx를 뽑고, 앞의 idx 선수와 리스트 교환
        call_index = players.index(call_player)
        players[call_index], players[call_index -1] = players[call_index -1], players[call_index]
    
    return players

제출했더니 시간초과. 

index 함수를 사용해서, index 를 모든 리스트에 대해 돌면서 찾는것은 

for 문안에, for 문을 한번 더 돌리는 것과 같은 시간 복잡도를 가졌다. 

 

2차 시간초과

index 함수를 쓰지 않고, enumerate 함수로 , 딕셔너리를 생성해서 

index 를 찾는 것을 해보았으나 

def solution(players, callings):
    for call_player in callings:
        players_dict = {name : idx for idx, name in enumerate(players)}
        # ex) kai 일때, kai 의 idx를 뽑고, 앞의 idx 선수와 리스트 교환
        call_index = players_dict[call_player]
        # print(call_index)
        players[call_index], players[call_index -1] = players[call_index -1], players[call_index]
        # print(players)
    return players

잘 생각해보니, for 문 안에서 enumerate 로 딕셔너리 생성하는 것 자체가 

같은 시간복잡도를 가짐. 

 

그래서 for 문 바깥에서 딕셔너리를 생성하고 

딕셔너리 안에 있는 요소들의 변동값을 for 문 안에서 처리하도록

리페토링 했다. 

def solution(players, callings):
		# for 문 바깥으로 enumerate 를 생성하면, for 문 내부에서 변동값을 저장해줘야함
    players_dict = {name : idx for idx, name in enumerate(players)}
    for call in callings:
        # ex) kai 일때, kai 의 idx를 뽑고, 앞의 idx 선수와 리스트 교환
        call_idx = players_dict[call]
        # 변동값을 저장하는 두 줄의 코드
        players_dict[call] -= 1 # 앞으로 한칸
        players_dict[players[call_idx-1]] += 1 # 뒤로 한칸
        
        players[call_idx], players[call_idx -1] = players[call_idx -1], players[call_idx]
        # print(players)
    return players

for 문 안에서의 index 함수와 enumerate 함수의 사용은 

n ** 2 의 시간복잡도를 가져온다는 것을 학습하게 되었다.