[코딩테스트] 달리기 경주

프로그래머스 lv.1 달리기 경주 문제를 풀어보았다.

 

 

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

프로그래머스

 

 

 

내가 처음에 생각한 코드이다.

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

 

 

(1) 이름이 불릴때마다 파이썬 내장함수 .index를 사용해서 그 선수의 인덱스를 찾고 (2) 바로 앞사람과 현재 순위를 바꿔준다. 문제를 보자마자 누구나 생각할 수 있을만한 간단한 코드이다. 

 

하지만 시간 초과가 나와서 힌트를 보고 풀어야만 했다 ㅜㅜ

 

 

정답은 다음과 같이 딕셔너리 자료형을 사용해서 시간복잡도를 줄이는 것이다.

def solution(players, callings):
    answer = []
    playerKey = {}
    numKey = {}
    
    for i in range(len(players)):
        playerKey[players[i]] = i+1
        numKey[i+1] = players[i]
    
    for i in callings:
        sco = playerKey[i]
        losePlayer = numKey[sco-1]
        
        playerKey[i], playerKey[losePlayer] = playerKey[losePlayer], playerKey[i]
        numKey[sco], numKey[sco-1] = numKey[sco-1], numKey[sco]
    
    for i in range(len(playerKey)):
        answer.append(numKey[i+1])
    
    return answer

 

player를 키로 갖는 딕셔너리와 순위를 키로 갖는 딕셔너리를 만들고, 이름이 불릴때마다 계속해서 바꿔주는 것이다.

 

 

 

 

딕셔너리 자료형

이게 왜 더 빠른지 이해하려면 리스트와 딕셔너리가 어떻게 내가 원하는 요소를 찾는지 알아야한다.

 

리스트 자료형의 경우, 내가 찾고자 하는 요소가 나올때까지 모든 요소를 순회한다. 코드상에선 .index 한줄로 끝나는 명령 같아도 내부적으로 for문을 통해 해당 요소를 찾으려 들기 때문에 결과적으론 O(n^2)의 시간복잡도를 갖는 셈이다.

 

딕셔너리 자료형의 경우, 내가 찾고자 하는 요소를 키값을 통해 바로 찾을 수 있다. 배열 전체를 순회하는 과정을 생략하기 때문에 결과적으로 O(n)의 시간복잡도를 갖는다.

 

이걸 개념적으로는 알고 있었는데 문제에 적용하는건 처음이라 발상을 못떠올렸다......