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

문제

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

 

얀에서는 매년 달리기 경주가 열린다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부른다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 "soe" 선수가 "mumu" 선수를 추월했다는 뜻이다.

현재 등수 순서대로 선수들의 이름이 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

 

접근

처음에는 다음과 같이 접근했다.

1. callings를 순서대로 접근한다.

2. players 배열에서 불린 선수의 등수를 찾는다.

3. 직전 선수와 순서를 바꾼다.

def solution(players, callings):
    for call in callings:
        i = players.index(call)
        players[i - 1], players[i]= players[i], players[i - 1]
    return players

이 방식은 값은 맞지만, players에서 호명한 선수를 찾을 때 최악의 경우 players의 최대 길이 * callings의 최대 길이만큼 값을 순회한다. 따라서 효율성 제한을 통과하지 못했다.

 

 

풀이

효율적으로 선수의 등수를 찾기 위해 선수의 이름를 key로 하고 선수의 등수를 value로 하는 딕셔너리를 사용했다.

 

1. 선수의 이름를 key로 하고 선수의 등수를 value로 하는 딕셔너리를 선언한다.

map_name_rank = {players[i]: i for i in range(len(players))}

 

2. 해설진이 호명한 선수의 등수를 찾는다. 그리고 추월 당한 등수를 찾는다.

passing_rank = map_name_run[call] # 추월한 등수
passed_rank = passing_rank - 1 # 추월 당한 등수

 

3. 각 선수의 등수를 저장하는 딕셔너리를 추월 이후 등수로 갱신한다.

map_name_rank[call] = passed_rank
map_name_rank[players[passed_rank]] = passing_rank

 

4. players의 순서를 추월 이후 상태로 갱신한다.

players[passed_rank], players[passing_rank] = players[passing_rank], players[passed_rank]

 

5. callings를 순회하면서 2 ~ 4번까지의 과정을 반복 수행한다.

전체 코드는 다음과 같다.

def solution(players, callings):
    map_name_rank = {players[i]: i for i in range(len(players))}
        
    for call in callings:
        passing_rank = map_name_rank[call]
        passed_rank = passing_rank - 1
        
        map_name_rank[call] = passed_rank
        map_name_rank[players[passed_rank]] = passing_rank
        players[passed_rank], players[passing_rank] = players[passing_rank], players[passed_rank]
        
    return players

 

 

 

참고 문서

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