프로그래머스 달리기 경주 문제 시간 초과

프로그래머스 레벨1 문제인 달리기 경주 문제에서 테스트 9 ~ 13번까지 시간 초과 에러가 발생했다.

아직 문제를 풀기 전 시간복잡도를 고려하는 것이 익숙하지 않아서 생긴 에러 였다.

 

내가 처음 작성한 답안은 아래와 같다.

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

 

결과값은 정답과 맞게 나오지만 시간초과 에러가 나오는 걸로 봐서는 index() 함수나 swap해주는 부분에서 문제가 있을 것 으로 예상된다. 하지만 swap해주는 부분보다는 index() 함수가 시간복잡도에 더욱 연관이 있을 것 같으니 index()함수에 대해 찾아보았다.

 

파이썬 index()함수의 시간복잡도는 O(n)이다.

(for문으로 길이가 n개인 리스트를 돌며 내가 찾는 값과 같은 값을 가지는 요소의 인덱스 값을 찾으려고 할 때 그 값이 가장 마지막에 있다면 최악의 시간복잡도 O(n)이 된다.)

 

 

달리기 경주 문제의 제한 사항을 보면 players와 callings의 범위가 주어지는데 아래와 같다.

 

5 ≤ players의 길이 ≤ 50,000

2 ≤ callings의 길이 ≤ 1,000,000 

 

그러면 내가 처음 작성한 코드는 최악의 경우 시간복잡도가 callings의 최대 길이 * players의 최대 길이 = 50,000 * 1,000,000 = 50,000,000,000 = 500억이 된다.

 

파이썬의 연산 시간이 대략 1초 당 2000만 번이라고 가정하면, 2500초가 걸린다는 것이다. 당연히 시간 초과 에러가 발생할 수 밖에 없다.

 

 

 

이럴 때는 딕셔너리 2개를 사용하거나 딕셔너리 1개, 리스트 1개를 사용하여 인덱스 번호를 저장하고 변경해주는 방법을 사용하면 된다.

 

먼저 players 배열을 기반으로 "선수의 이름: 인덱스 값"로 이루어진 딕셔너리를 하나 만든다.

 

그리고 선수의 순위(인덱스 값)가 바뀔 때마다 딕셔너리에서 해당 선수의 순위(인덱스 값)을 swap해주고, players 리스트 자체에서도 swap을 해준다. 그러면 index() 함수를 이용하지 않아도 딕셔너리를 통해서 해당 선수의 이름을 키값으로 그 선수의 순위(인덱스 값)를 탐색할 수 있다.

 

 

위의 방법으로 수정한 정답 코드는 아래와 같다.

def solution(players, callings):
    temp = {name: idx for idx, name in enumerate(players)}
    
    for name in callings:
        n = temp[name]
        
        temp[players[n]] = n - 1
        temp[players[n-1]] = n
        
        players[n], players[n-1] = players[n-1], players[n]
    
    return players