달리기 경주(프로그래머스) 문제풀이

 

문제 

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

프로그래머스

 

 

문제 접근 방식

선수들의 순서가 주어지고, 이름이 호명되면 앞의 선수와의 순서를 바꿔주는 구현 문제이다. 선수들의 이름을 통해서 players에서 해당 선수가 어디에 존재하는지를 판단한 후, 앞 사람과의 위치를 바꿔주면 된다. 이때, 호명한 사람이 어디에 있는지 파악할 때 가장 단순한 방법으로는 배열을 순회해서 찾을 수 있겠지만, 매번 호명을 할 때 마다 선형시간이 걸리기 때문에 비효율적이다. 

 

이를 해결하기 위해, 각 이름과 순서를 key-value 쌍으로 dict 에 넣어놓고 이름을 통해 순서를 바로 찾을 수 있도록 하였다.

rank_table=dict()
for i in range(len(players)):
    rank_table[players[i]]=i

 

 

시간 복잡도

이름과 순서를 key-value 쌍으로 저장해놓기 위해서 players의 수 만큼 순회를 해야하며, callings 의 이름 수 만큼 순서를 변경해줘야한다. 각각을 for 문으로 돌게 되고, 최대 길이가 각각 5e4, 10^6 d이기 때문에 시간 내에 동작한다.

 

코드

def solution(players, callings):
    # '이름':'순서' 를 key:value 쌍으로 갖는 테이블
    rank_table = dict()
    for i in range(len(players)):
        rank_table[players[i]] = i


    for name in callings:
        index = rank_table[name] #호명한 사람의 위치를 파악한다
        previous_name = players[index - 1] #앞 사람의 이름을 파악한다
        players[index - 1], players[index] = players[index], players[index - 1] # 두 사람의 위치를 바꿔준다

        # 테이블을 갱신한다
        rank_table[previous_name] = index
        rank_table[name] = index - 1

    return players