[programmers lv1.python] 달리기 경주 풀이 (시간초과 해결)

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

프로그래머스

문제

문제는 간단하다 ! 해설진이 이름을 부르는 선수는 달리기 경주 중 현재 자리에서 추월한 선수이므로, 선수들 리스트에서 한 칸 땡겨오면 되는 것!

 

1차 풀이 (시간 초과 실패)

def solution(players, callings):
    
    for call in callings:
        # 호출된 이름(call)의 현재 인덱스 찾기
        idx = players.index(call)
        # 첫 번째 원소가 아니라면 한 칸 앞으로 이동 
        if idx > 0:
            players[idx], players[idx - 1] = players[idx - 1], players[idx]
            
    return players

callings 리스트를 순회하면서 각 호출된 이름이 players에서 위치하는 인덱스를 찾고, 찾으면 해당 이름을 한 칸 앞의 원소와 자리 교환하여 한 칸 앞으로 이동시키는 구조인데 .. 시간 초과 실패가 떴다.

매번 players 리스트를 탐색하면서 이름의 위치를 찾는 구조가 원인인 듯 하다. (players.index(call))

 

시간 복잡도

index() 메서드는 리스트에서 특정 요소의 위치를 찾을 때 O(n) 의 시간 복잡도를 가지므로, callings 배열의 모든 호출에 대해 index()를 호출할 경우 전체 시간 복잡도는 O(m * n) 이 된다. (여기서 n은 players의 길이, m은 callings의 길이)

즉, players의 길이가 커지고 callings의 호출 횟수가 많아질 수록 시간 복잡도 면에서 불리한 코드가 된다!

 

그래서 이러한 구조를 어떻게 해결할 수 있을지 생각해보다가 dict 구조를 사용해서 코드를 고쳐보기로 했다.

 

---

2차 풀이 (성공!)

매번 players 리스트를 탐색하여 이름의 위치를 찾는 대신, 선수의 이름과 현재 등수를 바로 찾을 수 있도록 dict를 사용했다. 

def solution(players, callings):
    # 선수 이름을 키로, 현재 등수를 값으로 저장하는 딕셔너리
    player_positions = {player: i for i, player in enumerate(players)}
    
    for call in callings:
        curr_position = player_positions[call]   # 추월한 선수의 현재 위치
        
        # 앞에 있는 선수와의 자리 교환
        if curr_position > 0:
            front_player = players[curr_position - 1]
            
            # 자리 교환
            players[curr_position - 1], players[curr_position] = players[curr_position], players[curr_position - 1]
            
            # 딕셔너리에서 두 선수의 위치 정보 업데이트
            player_positions[call] -= 1
            player_positions[front_player] += 1
    
    return players

dict를 사용해 선수의 위치를 저장하고, 이를 통해 인덱스를 바로 찾을 수 있도록 한 코드다. dict의 키를 통해 위치를 바로 찾고 업데이트하는 연산은 평균적으로 O(1) 시간이 걸리기 때문에, 호출을 처리하는 시간 복잡도가 O(m)으로 감소할 것이라고 기대했다.

제출해보니 속도가 눈에 띄게 빨라졌다 !!! 

 

시간 복잡도

정리해보면, players 리스트와 player_positions 딕셔너리를 동시에 업데이트하므로 시간 복잡도는 O(n + m)이다 (n은 players의 길이, m은 callings의 길이).

따라서 players의 크기가 크고 callings의 호출 횟수가 많을 때(최대 n=50,000, m=1,000,000일 때) 딕셔너리를 사용하는 방법이 훨씬 효율적이라는 말 ~~

 

<효율성 비교>

• 1차 코드: 시간 복잡도 O(m * n) (매번 리스트에서 index()를 찾음)
• 2차 코드: 시간 복잡도 O(n + m) (초기 딕셔너리 생성 O(n), 호출 순회 O(m))