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

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

프로그래머스

 

• 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부름
• 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때,해설진이 "soe"선수를 불렀다면
  • 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것
  • 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀜
• 선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return

제한사항

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

 

"""
입출력 예시)

players = ["mumu", "soe", "poe", "kai", "mine"], callings = ["kai", "kai", "mine", "mine"] -> ["mumu", "kai", "mine", "soe", "poe"]
"""

 

# players = ["mumu", "soe", "poe", "kai", "mine"], callings = ["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등이 되고 경주가 끝남
# => ["mumu", "kai", "mine", "soe", "poe"]

 

 

## 의사코드 ##

# 2개의 딕셔너리 활용

# 선수 딕셔너리
# player_dic = {p:i for i, p in enumerate(players)}

# 등수 딕셔너리 
# idx_dic = {i:p for i, p in enumerate(players)}

# for call in callings:
      # 선수 딕셔너리 업데이트) 현재 선수의 등수는 앞 등수로, 앞 선수의 등수는 현재 등수로 swap 
      # 등수 딕셔너리 업데이트) 현재 등수의 선수를 앞 선수로, 앞 등수의 선수를 현재 선수로 swap 

# 1등 선수부터 배열로 출력 
# list(idx_dic.values())

 

 

 

통과한 코드

 

def solution(players, callings):
    # 선수 딕셔너리
    player_dic = {p:i for i, p in enumerate(players)}
    # 등수 딕셔너리
    idx_dic = {i:p for i, p in enumerate(players)}
    for call in callings:
        # 현재 등수
        cur_idx = player_dic[call]
        # 앞 등수
        front_idx = cur_idx - 1

        # 현재 선수 = call
        # 앞 선수
        front_player = idx_dic[front_idx]

        # 선수 딕셔너리 업데이트) 현재 선수의 등수는 앞 등수로, 앞 선수의 등수는 현재 등수로 swap 
        player_dic[call], player_dic[front_player] = front_idx, cur_idx
        # 등수 딕셔너리 업데이트) 현재 등수의 선수를 앞 선수로, 앞 등수의 선수를 현재 선수로 swap 
        idx_dic[cur_idx], idx_dic[front_idx] = front_player, call 

    # 1등 선수부터 배열로 출력 
    return list(idx_dic.values())

 

 

-> 2개의 딕셔너리를 활용해서 추월한 현재 선수와 추월당한 앞 선수의 이름과 등수를 각각 swap 

 

 

• 과정 확인

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

"""
호명된 선수(현재 선수): kai
현재 선수의 현재 등수: 3
앞 선수: poe
앞 선수의 등수: 2 

업데이트된 선수 딕셔너리: {'mumu': 0, 'soe': 1, 'poe': 3, 'kai': 2, 'mine': 4}
업데이트된 등수 딕셔너리: {0: 'mumu', 1: 'soe', 2: 'kai', 3: 'poe', 4: 'mine'}
--------------------------------------------------
호명된 선수(현재 선수): kai
현재 선수의 현재 등수: 2
앞 선수: soe
앞 선수의 등수: 1 

업데이트된 선수 딕셔너리: {'mumu': 0, 'soe': 2, 'poe': 3, 'kai': 1, 'mine': 4}
업데이트된 등수 딕셔너리: {0: 'mumu', 1: 'kai', 2: 'soe', 3: 'poe', 4: 'mine'}
--------------------------------------------------
호명된 선수(현재 선수): mine
현재 선수의 현재 등수: 4
앞 선수: poe
앞 선수의 등수: 3 

업데이트된 선수 딕셔너리: {'mumu': 0, 'soe': 2, 'poe': 4, 'kai': 1, 'mine': 3}
업데이트된 등수 딕셔너리: {0: 'mumu', 1: 'kai', 2: 'soe', 3: 'mine', 4: 'poe'}
--------------------------------------------------
호명된 선수(현재 선수): mine
현재 선수의 현재 등수: 3
앞 선수: soe
앞 선수의 등수: 2 

업데이트된 선수 딕셔너리: {'mumu': 0, 'soe': 3, 'poe': 4, 'kai': 1, 'mine': 2}
업데이트된 등수 딕셔너리: {0: 'mumu', 1: 'kai', 2: 'mine', 3: 'soe', 4: 'poe'}
--------------------------------------------------

['mumu', 'kai', 'mine', 'soe', 'poe']
"""

 

 

 

다른 풀이

 

def solution(players, callings):
    player_indices = {player: index for index, player in enumerate(players)}

    for j in callings:
        current_index = player_indices[j]
        desired_index = current_index - 1
        if current_index > 0 and players[desired_index] != j:
            players[current_index], players[desired_index] = players[desired_index], players[current_index]
            player_indices[players[current_index]] = current_index
            player_indices[players[desired_index]] = desired_index

    return players

 

 

-> 하나의 딕셔너리만 활용

 

 

 

 

 

참고)

 

https://security-nanglam.tistory.com/427

[python] List to Dict (리스트를 딕셔너리로 변환) 총 정리!!

 

https://prod.velog.io/@heyggun/4%EC%BD%941%ED%8C%8C-94.-LV-1.-%EB%8B%AC%EB%A6%AC%EA%B8%B0-%EA%B2%BD%EC%A3%BC

[4코1파] #94. LV 1. 달리기 경주