[프로그래머스] 달리기 경주 (파이썬, 시간복잡도 개선)

[문제]

callings에 등장하는 항목을 앞 항목하고 바꿔치기하는 문제였다.

시간복잡도를 고려하는 게 문제의 포인트였다.

 

 

 

[코드]

처음에는 아무 생각 없이 아래와 같이 코드를 짰다. 

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

 

for문 안에서 i의 인덱스 찾아서 앞 항목과 바꿔치기하는 방법을 사용했다.

 

 

 

[왜 틀렸나]

시간초과가 떴다.

players의 길이가 50,000개 이하, callings의 길이가 1,000,000개 이하인 상황에서 for문 안에 index를 넣었더니

시간복잡도가 $O(NM)$이 되어버렸다.

둘 중 하나를 어떻게든 처리를 해줘야 했다.

for문을 처리하긴 쉽지 않으니 시간복잡도 $O(N)$인 index를 시간복잡도 $O(1)$인 딕셔너리로 바꿔줬다.

그래서 최종 시간복잡도 $O(N+M)$으로 통과를 했다.

 

 

 

[개선 코드]

앞에서 player를 player_index 딕셔너리 형태로 만들고 시작했다.

(+참고: player_index = {'mumu':0, 'soe':1, 'poe':2, 'kai':3, 'mine':4}) 

def solution(players, callings):
    player_idx = {player: idx for idx, player in enumerate(players)}

    for i in callings:
        idx = player_idx[i]
        prev_idx = players[idx - 1]
        players[idx - 1], players[idx] = players[idx], players[idx - 1]
        player_idx[i] -= 1
        player_idx[prev_idx] += 1

    return players

 

 

 

 

[알게된 점, 느낀점]

이제는 시간복잡도를 고려하면서 코드를 짤 때가 되었음을 느낀다.

값 범위 보고 시간복잡도가 얼마나 나올지 각을 재보자

그리고 index가 시간복잡도 $O(N)$인 것도 의식하고, 필요하다면 딕셔너리 형태로 만들어서 코드 짜는 것도 고려해보자