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

링크

문제 설명

def solution(players: List[str], callings: List[str]) -> List[str]:
        ...

callings는 players의 원소로만 이루어져 있다. callings의 원소를 players에서 찾아 i - 1 위치의 원소와 순서를 서로 바꿔준다. 모든 callings의 원소에 대해 순서를 바꿔준 결과를 반환하면 된다.

제한사항

• 5 ≤ players의 길이 ≤ 50,000
  • players[i]는 i번째 선수의 이름을 의미합니다.
  • players의 원소들은 알파벳 소문자로만 이루어져 있습니다.
  • players에는 중복된 값이 들어가 있지 않습니다.
  • 3 ≤ players[i]의 길이 ≤ 10
• 2 ≤ callings의 길이 ≤ 1,000,000
  • callings는 players의 원소들로만 이루어져 있습니다.
  • 경주 진행중 1등인 선수의 이름은 불리지 않습니다.

풀이

단순히 리스트의 index와 insert함수를 사용할 수도 있지만 callings의 최대 길이가 100만, players의 길이가 5만이기 때문에 최악의 경우 100만 x 5만의 시간이 걸리게 된다. 따라서 선수의 등수를 저장하는 dictionary를 추가적으로 선언해 문제를 풀었다. 이 dictionary의 키는 선수의 이름, 값은 등수로 생성한다. 그러면 선수 이름만으로 players 배열에서의 위치를 바로 알 수 있게된다. index의 시간복잡도가 O(n)인 것을 생각하면 더 빠르게 동작한다.

제출코드

def solution(players: List[str], callings: List[str]) -> List[str]:
    players_dict = {v: i for i, v in enumerate(players)}
    for c in callings:
        i = players_dict[c]
        players[i], players[i - 1] = players[i - 1], players[i]
        players_dict[players[i]] = i
        players_dict[players[i - 1]] = i - 1
    return players