달리기 경주

문제 설명

현재 달리고 있는 선수들의 목록이 주어진다. 이때 해설진들은 순서가 앞으로 한 칸 가는 선수의 이름만 부른다. 게임이 끝났을 때 현재의 등수를 구하는 문제다.

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

프로그래머스

문제 풀이

첫 번째 풀이

처음에는 단순히 배열에다가 넣어주고 선수 한 명이 나오면 해당 배열에서 선수의 위치를 찾아준 다음에 앞에 있는 선수와 바꿔주는 방식을 이용했다. 그러나 이런 방식은 n^2이 되어서 시간 초과가 난다. 당장 한 번씩 돌려줘야 하는 callings도 최대 길이가 1,000,000이니...

두 번째 풀이

어떻게 할까 하다가 dic를 이용하는 아이디어를 봤다. dic를 두 개 만들어서 하나는 등수를 key로 선수 이름을 value로 맞춰주고 다른  dic는 key로 rank를 value로 선수 이름을 맞춰준다.

 

다음 callings를 한 번씩 돌면서 현재 선수의 이름, 위치, 앞에 있는 선수의 이름, 위치를 구해준다. 다음에 이 둘을 바꿔주면 된다. 내가 처음 본 아이디어는 dic를 두 개 사용하는 것이었지만, 다른 사람의 풀이를 살펴 본 결과 dic를 한 번만 사용할 수 있다는 것을 알게 되었다.

코드

python

def solution(players, callings):
    answer = []
    # 등수->선수
    rank ={index:player for index, player in enumerate(players)}
    # 선수->등수
    playersRank = {player:index for index, player in enumerate(players)}
    
    for calling in callings:
        currentRank = playersRank[calling]
        frontRank = currentRank - 1
        frontPlayer = rank[frontRank]
        
        # 현재 등수를 앞에 있는 선수의 등수와 바꿔준다.
        rank[currentRank] = frontPlayer
        rank[frontRank] = calling
        
        # 등수를 선수에 맞춰서 바꿔준다.
        playersRank[calling] = frontRank
        playersRank[frontPlayer] = currentRank
    
    for i in range(len(players)):
        answer.append(rank[i])
        
    return answer