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

문제설명

얀에서는 매년 달리기 경주가 열립니다. 

해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 

예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 

해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 

 

즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 

해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 

경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

제한사항

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

 

입출력 예

players	callings	result
["mumu", "soe", "poe", "kai", "mine"]	["kai", "kai", "mine", "mine"]	["mumu", "kai", "mine", "soe", "poe"]

 

 

문제해설

이번 문제는 난이도가 레벨 1에 해당하지만, 생각보다 가볍게 덤비긴 어려웠다.

 

가장 큰 문제는 입력의 크기이다.

이 문제를 풀기 위해선 반드시 callings의 모든 원소를 한 번 확인해야 한다.

여기서 최대 100만의 데이터를 순회하는데,

이 순회 과정에서 players를 한 번이라도 확인하게 된다면, 5만의 순회가 중첩된다.

 

결론적으로 50,000 x 1,000,000 으로 일반적인 문제의 제한 시간을 아득히 초과한다.

 

이 문제는 자료구조를 잘 확인해야 되는 문제이다.

 

시간초과가 발생하지 않도록 반드시 상수시간의 알고리즘을 사용해야만 한다.

 

총 두 가지 방법이 존재한다.

 

1. 두 개의 Hash 사용해서 순위를 실시간으로 업데이트

2. 하나의 Hash를 사용해서 List를 실시간으로 업데이트한다.

 

본인은 전자의 방식으로 문제를 해결했다.

 

Hash 자료구조는 접근에 O(1)의 시간이 소요된다.

따라서 두 개의 해쉬를 사용하는데, 이 때 키값과 밸류는 서로 반전된 구조로 선언한다.

 

하나의 키값을 알 수 있으면, 그 때의 value도 같이 불러올 수 있게 된다.

 

따라서 선수의 이름을 받으면 그 선수의 이전 등수와 현재 업데이트 하고자 하는 등수를 알 수 있고

 

그 등수를 알게 되면, 기존에 있던 선수의 이름과 현재의 등수를 업데이트할 수 있게 되는 것이다.

 

설명이 어려웠는데, 정답코드를 보면서 다시 읽어보면 금방 이해할 수 있을 것이다.

 

정답코드

def solution(players, callings):
    prize_dict = {i+1:player for i, player in enumerate(players)}
    now = {player:i+1 for i, player in enumerate(players)}
    
    for call in callings:
        now_prize = now.get(call)
        
        slayer = prize_dict[now_prize-1]
        prize_dict[now_prize-1] = call
        prize_dict[now_prize] = slayer
        
        now[slayer] = now_prize
        now[call] = now_prize-1
        
    return list(prize_dict.values())