[Lv.1] 달리기 경주

[문제 설명]

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

---

 

[문제 해결 아이디어]

player_index 딕셔너리에 players들의 현재 위치 index들을 저장해줍니다.

그 후 callings를 반복문을 돌려 각 위치를 바꿔준 후 

player_index에 초기화 해줍니다.

---

[코드]

def solution(players, callings):
    
    #players index 저장 dic
    players_index = {}
    
    for i, player in enumerate(players):
        players_index[player] = i
    
    #순서 바꾸기
    for call in callings:
        call_index = players_index[calling]
        
        players[call_index - 1],players[call_index] = players[call_index],players[call_index - 1]
        
        
        players_index[players[call_index]] = call_index
        players_index[players[call_index - 1]] = call_index - 1
        
    
    return players

 

---

[메모]

def solution(players, callings):
    for call in callings:
        c_index = players.index(call)
        players[c_index - 1], players[c_index] = players[c_index], players[c_index - 1]

위의 코드가 더 간결하지만 시간 초과 결과가 나온다.

 

주어진 두 코드의 가장 큰 차이점은 players_index 딕셔너리를 사용하여 players 리스트의 값과 해당 인덱스를 매핑하는 부분입니다.

두번째 에서는 players.index(call)을 호출하여 call 값을 players 리스트에서 찾고 해당 값의 인덱스를 반환합니다. 이 과정은 매번 callings 리스트의 요소마다 수행되며, 선형 시간(O(n))이 소요됩니다. 따라서, 전체 코드의 시간 복잡도는 O(n) × O(1) = O(n)입니다.

 

반면에 첫 번째 코드에서는 players_index라는 딕셔너리를 사용하여 players 리스트의 값과 해당 인덱스를 미리 매핑합니다. 이렇게 매핑된 딕셔너리를 통해 players_index[calling]을 조회하여 바로 해당 값의 인덱스를 얻을 수 있습니다. 딕셔너리 조회는 평균적으로 상수 시간(O(1))에 이루어지기 때문에, for 루프에서의 연산은 선형 시간(O(n))이 소요됩니다.

 

따라서, 첫번째 코드에서는 딕셔너리를 사용하여 players 리스트의 값과 인덱스를 미리 매핑함으로써 players.index(call) 호출을 피하고, 딕셔너리 조회를 통해 바로 인덱스를 얻을 수 있어 전체적인 성능이 개선됩니다.