[알고리즘] 프로그래머스 | 달리기경주

달리기 경주

답: 

def solution(players, callings):
    player = {} # 이름 : 등수
    ranking = {} # 등수 : 이름
    
    for i, p in enumerate(players):
        player[p] = i
        ranking[i] = p
        
    for call in callings:
        idx = player[call] 
        pre_idx = idx-1 
        pre_call = ranking[pre_idx] 
        
        ranking[pre_idx], ranking[idx] = call, pre_call
        player[pre_call], player[call] = idx, pre_idx

    answer = sorted(player, key=lambda x : player[x]) 
    return answer

 

 

문제 분석 및 해석

현재 순서가 담긴 players,

callings에 있으면 1등수 추월한다

 

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

해설진이 부른 이름을 담은 문자열 배열 callings

경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return

 

 

 

>> 풀이생각

단순히 List위치를 재 지정해주는 문제라고 생각했지만,

제한 사항에 주어진 케이스가 매우 많으므로 그때그때 지정해주면 시간초과가 발생한다

 

 

풀이를 쪼개어 생각해볼 수 있다.

 1) 선수 위치 찾기 (현재 선수의 이름과 위치와, 이전 등수 선수의 이름과 위치)

 2) 찾은 정보로 위치 재지정하기

 

양방향 인덱싱,  2개의 dictionary를 활용하는 문제였다

 

 

리뷰.

 

안될걸 알면서 여러가지 방법을 도전해보았는데, 딕셔너리 쓰는 연습이 되어 재미있는 문제였다

 

 

1. 해당 선수가 불리는 경우를 모두 찾아서 한번에 앞으로 이동시켜주는 방법

2. 한 번에 추월하는 경우를 모아서 그때그때 바꾸어 주는 방법 등등

 

두 방법 모두 index()함수를 활용하면서 최악의 경우 O(N^2)의 상태를 가져 계속 시간초과로 통과하지 못함.