[Python] 해쉬 문제 - 달리기 경주 (Programmers)

프로그래머스의 hash 관련 문제를 풀어봤습니다. 

처음에 일반적이 배열로 풀었는데, 문제를 자세히 보니까, input 값이 백만개가 될 수 있었습니다. 

즉, 일반적인 방식으로는 성능의 문제가 발생하기 때문에 '해쉬'를 사용 하였습니다. 

 

문제설명

얀에서는 매년 달리기 경주가 열립니다.
해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다.
예를 들어 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"]

4등인 "kai" 선수가 2번 추월하여 2등이 되고 앞서 3등, 2등인 "poe", "soe" 선수는 4등, 3등이 됩니다.
5등인 "mine" 선수가 2번 추월하여 4등, 3등인 "poe", "soe" 선수가 5등, 4등이 되고 경주가 끝납니다.
1등부터 배열에 담으면 ["mumu", "kai", "mine", "soe", "poe"]이 됩니다.

 

---

알고리즘 및 고려사항

• 입력받은 선수를 딕셔너리로 변환 한다
  • {이름:등수} 형태의 p_dic 과 {등수:이름} 형태이 location_dic 을 만듦
  • 이름, 등수를 key로 빠르게 찾기 위함
  • 입력값이 100만개까지 증가하므로, 탐색 알고리즘은 탐색 비용이 상수값인 딕셔너리를 활용
• 기본알고리즘
  1. 이름 key ,등수 key 인 딕셔너리 생성
  2. 입력받은 calling 리스트를 하나씩 가져와서 이름 key인 딕셔너리 탐색
  3. 이때, 찾은 등수, 앞 등수, 앞 선수 이름을 찾음
  4. 찾은 이름으로 p_dic의 등수는 감소(올림)시키고, 앞 선수 등수는 증가 시킴(내림)
  5. 등수 key 딕셔너리도 이름을 서로 변경시킴
  6. calling 을 끝내면, p_dic을 등수로 다시 정렬(튜플로 변환후 두번째 등수로 정렬)후 딕셔너리 반환
  7. 딕셔너리의 key인 이름만 list로 변환

프로그램 소스

def solution(players, callings):
    
    # 딕셔너리 탐색은 갯수가 증가해도 속도가 상수로 유지되므로, 딕셔너리 활용한다. calling이 100만개이므로
    p_dic = {player:i+1 for i,player in enumerate(players)}
    location_dic = {i+1:player for i,player in enumerate(players)}

    for c in callings:
        c_loc = p_dic[c]    # 리스트에 찾은 선수 등수를 c_loc 저장
        front = c_loc - 1   # 찾은 선수 이전 등수를 front 저장
        front_p = location_dic[front]   # location_dic 에서 이전선수 이름을 front_p 에 저장
        
        # 이름이 key인 딕셔너리를 수정
        p_dic[c] -= 1       # 현재 찾은 선수의 등수를 올림 (value를 -1)
        p_dic[front_p] += 1 # 앞 선수의 등수를 내림 (value를 +1) 
        
        # 등수가 key인 딕셔너리를 수정
        location_dic[c_loc] = front_p  # 현재 선수의 위치의 이름을 이전 선수로 변경
        location_dic[front] = c # 앞선수 위치의 이름을 현재선수로 변경


    # 이름 key 딕셔너리를 튜플로 변경후 두번째요소(등수)로 정렬해서 다시 딕셔너리로 반환
    p_dic = dict(sorted(p_dic.items(),key=lambda x:x[1]))
    # p_dic 의 key값(이름)을 배열로 반환
    answer = list(p_dic.keys())

    return answer

 

코딩 팁( Tip )

# dictionary = { idx : element   for  element  in  enumerate ( list ) }
# enumerate를 통해서 value를  세팅함
p_dic = { player :  i+1  for i, player in enumerate( players ) }