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

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

프로그래머스

 

 

사용 알고리즘: 없음 -> 구현

 

 

제한 사항

• 5 <= players 의 길이 <= 50,000
  • players[i] 는 i 번째 선수 이름 의미
  • players 의 원소들은 알파벳 소문자로만 이루어짐
  • players 에는 중복된 값 x
  • 3 <= players[i] 의 길이 <= 10
• 2 <= callings 의 길이 <= 1,000,000
  • callings 는 players 의 원소들로만 이루어져 있음
  • 경주 진행중 1응인 선수의 이름은 불리지 않음

 

callings 의 길이 만큼 돌면서 매 턴마다 index 나 find 함수를 사용해서 구현한다고 하면,

딱 봐도 시간초과 될 것 같은 느낌이 오는 제한사항..

 

-> index 나 find 함수는 O(n) 시간의 시간 복잡도를 가진다. (players 배열을 다 돌면서 원하는 요소를 찾는데 걸리는 시간)

그러니 시간 복잡도를 대충만 계산해도 O(callings 길이) * O(n) = 1,000,000 * 50,000 = 50,000,000,000 (무려 오백억..) 의 시간이 걸리기 때문에 그렇게 풀었을 때 통과될 리 없다!

 

 

그럼 어떤 식으로 원하는 요소를 찾아야 할까?

-> 딕셔너리를 사용

딕셔너리는 해쉬 테이블이라는 내부구조를 사용하여, 빠른조회/빠른 삽입과 삭제/리스트보다 빠른 탐색을 제공한다.

(조회, 삽입/삭제: O(1), 탐색: 평균 O(1) 시간의 시간 복잡도를 가지며, 최악의 경우 O(n) 시간의 시간 복잡도 가짐)

 

 

그럼 코드를 살펴보자.

(사실 딕셔너리만 사용했다뿐이지 find, index 를 사용하는 코드와 구현 로직은 동일할 것이다.)

 

player이름:인덱스(현재순서) 의 키:값으로 딕셔너리를 만들었다. 

이렇게 딕셔너리를 만들면 호명된 선수의 이름을 키 값으로 넣었을 때 현재 그 선수 의 인덱스(순서)를 빠르게 찾을 수 있다.

 

그리고 추월을 할 선수의 인덱스(현재 뒤에 있는)를 backIndex 에 저장하고, 추월을 당할 선수의 인덱스(현재 앞에 있는)를 frontIndex 에 저장하였다. 

 

딕셔너리를 통해 호명된 선수들의 순서를 계속 찾을 것이므로 순서가 바뀌면 갱신해줘야 하기 때문에 딕셔너리 갱신을 해주었다. 

그리고 현재 선수들의 순서인 players 배열의 순서를 바꾸어 주었다. 

def solution(players, callings):
    answer = players
    # player이름:인덱스 -> 이런 키:값 쌍으로 딕셔너리 만듦
    playersDict = {player: index for index, player in enumerate(players)}
    for i in range(len(callings)):
        backIndex = playersDict[callings[i]] # 원래 뒤에 있었지만 추월을 할 player 인덱스, 현재 뒤에 있는
        frontIndex = backIndex - 1 # 원래 앞에 있었지만 추월 당할 player 인덱스, 현재 앞에 있는
        
        # 딕셔너리에 인덱스 갱신
        playersDict[players[backIndex]] = frontIndex 
        playersDict[players[frontIndex]] = backIndex
        # player 배열의 앞뒤 순서 바꿈
        players[backIndex], players[frontIndex] = players[frontIndex], players[backIndex]
    return answer

 

 

 

시간 복잡도

 

- 딕셔너리 생성 부분

playersDict = {player: index for index, player in enumerate(players)} # O(n)

 

일단 playersDict 를 만드는데 O(players 배열의 길이) 만큼의 시간이 걸린다. 

-> players 배열의 길이를 n 이라고 했을 때 O(n) 시간 복잡도를 가진다. 

 

 

- for 루프

for i in range(len(callings)): # O(callings의 길이) * O(1)
    backIndex = playersDict[callings[i]]
    frontIndex = backIndex - 1
    playersDict[players[backIndex]] = frontIndex
    playersDict[players[frontIndex]] = backIndex
    players[backIndex], players[frontIndex] = players[frontIndex], players[backIndex]

 

callings 의 길이를 m 이라고 했을 때, 루프를 도는 데 O(m) 시간이 걸린다.

각 턴에서 딕셔너리의 벨류 값에 접근하는 데에는 O(1) 시간이 걸린다. 

-> for 루프는 O(m) * O(1) = O(m) 시간의 시간 복잡도를 가진다. 

 

 

총 시간 복잡도를 구해보자.

 

총 시간 복잡도는 O(n) + O(m) = O(n + m) 인데, 아마 O(m) 에 가까울 것이다. 

(m 의 최대값은 1,000,000, n 의 최대값은 50,000,  m >>> n 이라서)