PROG LV1 : 달리기 경주 (python)

문제

 

프로그래머스

 

간단한 구현 문제인데, 시간 복잡도를 생각해야 하는 문제이다.

 

 

 

풀이 방법

 

접근 방법이 완전 틀린 건 아니었는데, 내가 처음에 풀었던 방식은 계속 호명한 이름을 찾을 때까지 반복문을 돌기 때문에 시간 초과가 발생했다.

 

 

그래서 링크를 기준으로(키값으로) 선수 이름을 저장하는 딕셔너리와 선수 이름을 기준으로(키값으로) 등수를 저장하는 딕셔너리 두 개를 통해 해당 시간 초과 문제를 해결할 수 있었다.

 

 

 

코드

 

######## 시간 초과 코드 ########

def solution(players, callings):
    answer = []
    
    for x in callings:
        for idy, y in enumerate(players):
            if idy!= 0 and x == y:
                players[idy-1], players[idy] = players[idy], players[idy-1]
                break
                
    answer = players
    return answer

 

######## 정답 코드 ########

def solution(players, callings):
    
    rank = {} # 순위: 선수 이름
    player = {} # 선수 이름: 순위
    
    for idx, x in enumerate(players):
        rank[idx] = x
        player[x] = idx
        
    for y in callings:
        this_rank = player[y] # 현재 불린 선수 순위
        prev_rank = this_rank - 1 # 불린 선수 순위 앞 순위
        prev_person = rank[prev_rank] # 불린 선수 순위 앞 사람 이름
        
        rank[prev_rank], rank[this_rank] = rank[this_rank], rank[prev_rank]
        player[prev_person], player[y] = player[y], player[prev_person]
    
    answer = list(rank.values())
    
    return answer