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

문제 출처 : 프로그래머스

 

문제는 여기에

---

문제

• 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부른다.
• 2등인 선수의 이름을 부른다면 그 선수는 1등이 되었다는 것
• 선수들의 이름이 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등인 선수의 이름은 불리지 않습니다.

입출력 예

 

접근

처음에 시도 했을 때는 시간 초과로 실패했었다.

1. 불린 선수의 이름이 players의  몇 번째 인덱스에 있는지 조사
2. (1)에서 조사한 인덱스와 바로 전 인덱스와의 교환

풀이

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

    return players

테스트 9 ~ 13에서 시간 초과가 나온다

고찰

위 코드에서 비효율적인 부분은 호명된 선수의 idx 하나를 구하려면 1,000,000 X 50,000 번을 왕복해야한다.

아마 이 부분이 시간 초과의 원인일 것이다.

선수의 인덱스를 어떻게 빨리 찾을 수 있을까? 생각해봤는데 딕셔너리를 이용하면 쉽게 풀 수 있다고 하여 시도해보았다.

 

접근2

1. {선수:등수}, {등수:선수} 의 두 딕셔너리를 만든다.
2. calling을 반복문으로 돌며, 해당 선수와 앞 등수의 선수 두 딕셔너리를 모두 수정해준다. 
3. 등수 딕셔너리 키의 값만을 출력한다.

풀이

def solution(players, callings):
    idx = {i:player for i, player in enumerate(players)}  # {등수:선수} 딕셔너리 생성
    p = {player:i for i, player in enumerate(players)}  # {선수:등수} 딕셔너리 생성
    
    for i in callings:
        loc = p[i]  # 호명된 선수의 현재 등수
        pre = idx[loc-1]  # 앞 선수
        
        idx[loc] = pre  # 앞 선수의 등수를 다운
        idx[loc-1] = i   # 호명된 선수를 앞 등수로 업
        
        p[i] = loc-1
        p[pre] = loc
        
    return list(idx.values())

 

무사 통과!

 

딕셔너리 배우기만 하고 문제에 적용해보지를 못했는데, 완벽하게 이해는 못해도 경험했다는 것에 만족!