[프로그래머스] 달리기 경주 - 해시

[ 문제링크 ]

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

 

🚩 조건

1. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부름
2. 선수들의 이름이 1등부터 현재 등수부터 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어지면, 경기가 끝났을 때 등수 순서대로 배열에 담아 return해라

 

 

🚩 접근

그냥 단순히 swap 형태로 구현하면..?

 

 

🚩 시행착오

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

위와 같이 callings 배열을 돌며 순위를 찾고 바꾸는 과정은 몇몇 테스트 케이스에서 시간초과가 발생한다. list에서 item의 인덱스를 찾아 반환하는 index(item) 메서드의 시간복잡도는 O(n)이고, players 길이는 최대 50,000, callings 길이는 최대 1,000,000이므로 반복 횟수 또한 많으므로 시간 초과가 발생하는 것이다. (아마 시간 초과가 난 테케는 그런 경우겠지?)

 

따라서 매 반복마다 O(n)의 연산을 하지 않고, 더 효율적으로 선수들의 순위, 즉 index를 찾을 수 있는 방법을 생각해야 한다. 그 중 하나가 해시 맵을 사용하는 것이다. 

 

해시 맵이란 키(Key)와 값(value)쌍을 저장하는 자료 구조이다. insert, erase, find, update 연산이 모두 O(1)에 처리 가능하다.

파이썬에서 해시는 딕셔너리를 통해 구현할 수 있다!

 

키가 선수, 값이 (등수-1)인 딕셔너리 result를 만들고, callings 배열을 돌며 이름이 등장할 때마다 그 이름을 result 배열에서 찾아 현재 등수를 알아내고, 수정한 후 업데이트하여 다시 저장한다. 그리고 이 선수에게 추월당한 선수를 알아내는 방법은 players 배열을 참고하면 된다! (이 사고가 나름 신박하게 느껴졌다..)

 

 

💻 코드 (Python3)

def solution(players, callings):
    result = {player:i for i,player in enumerate(players)}
    
    for name in callings:
        idx=result[name]
        result[name]-=1
        result[players[idx-1]]+=1
        players[idx], players[idx-1] = players[idx-1], players[idx]
    return players