프로그래머스 | 달리기 경주 [파이썬 python]

프로그래머스

 

처음 시도한 코드

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

그냥 swap 하면 쉽게 풀리는 문제 아닌가?라고 덤벼들었다가 시간 초과를 만나게 되었다.

calling의 최대 길이가 1,000,000이고, players의 최대 길이가 50,000이기 때문에 idx 하나를 구하기 위해선 1,000,000 × 50,000번을 반복해야 한다.

내 머리로는 어떻게 해야 할지 해결책이 떠오르지 않아서 다른 사람들의 풀이를 보다 보니 공통적으로 딕셔너리를 사용한 걸 볼 수 있었다.

 

정답 코드

def solution(players, callings):
    result = {player: i for i, player in enumerate(players)} # 선수: 등수
    for who in callings:
        idx = result[who] # 호명된 선수의 현재 등수
        result[who] -= 1 # 하나 앞 등수로 바꿔줌 -1
        result[players[idx-1]] += 1 # 앞에 위치했던 선수의 등수 +1
        players[idx-1], players[idx] = players[idx], players[idx-1] # 위치 변경
    return players

idx를 구하는 시간을 줄이기 위해 선수:등수 형태로 구성된 딕셔너리 result를 만들어주었다.

이 result에는 호명 될때마다 바뀌는 선수별 등수를 저장해 줄 것이고, 이를 이용해서 호명되는 선수의 현재 등수(=인덱스)를 구할 것이다.

 

callings에 담긴 선수들의 이름을 하나씩 가져온다.

해당 선수가 현재 몇 등인지 result에서 찾아 idx에 저장한다.

그런 다음, 방금 호명된 선수는 바로 앞사람을 추월한 것이므로 -1를 하여 하나 앞 등수로 바꿔준다.

그럼 추월당한 선수는 하나 뒷 등수로 바꿔주어야 한다.

이 선수는 players에서 idx-1에 위치했던 선수이고, 등수 반영을 위해 result에서 이 선수에 해당하는 등수를  +1 해준다.

마지막으로 두 선수의 바뀐 위치를 swap을 이용하여 players에 반영해 준다.

나는 선수:등수 딕셔너리 하나만 만들었지만, 다른 사람들의 코드를 보면 선수:등수, 등수:선수 두 개의 딕셔너리를 만든 경우가 많다.

매번 추월한 선수가 호명될 때마다 swap 하지 않고, 등수:선수에도 동시에 반영하면 최종 결과를 리턴할 때 더 빠른 시간에 실행이 가능하다.