[프로그래머스] Lv1 - 달리기 경주

문제

프로그래머스 연습문제

• Lv 1. 달리기 경주 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/178871

코드 구현

def solution(players, callings):

    players_dict = dict()       # 사전 선언

    # 사전에 players 배열 값 세팅하기 (key : 선수이름, value : 인덱스)
    for i, player in enumerate(players):
        players_dict[player] = i

    # 시간 초과 난 이전 코드
    # for i in range(len(callings)):
    #     overtake_index = players.index(callings[i])
    #     passed_index = players.index(callings[i]) - 1
    #
    #     overtake = players[overtake_index]
    #     players[overtake_index] = players[passed_index]
    #     players[passed_index] = overtake

    for i in callings:
        overtake_index = players_dict.get(i)    # 사전으로 추월하는 선수의 인덱스 탐색하기

        players_dict[players[overtake_index]] -= 1          # 추월하는 선수 인덱스 값 바꿔주기 (추월 했으니까 -1)
        players_dict[players[overtake_index - 1]] += 1      # 추월 당하는 선수 인덱스 값 바꿔주기 (추월 당했으니까 +1)

        players[overtake_index], players[overtake_index - 1] = players[overtake_index - 1], players[overtake_index]     # players 배열에서 순서 바꿔주기

    return players

풀이

• for문으로 추월하는 선수, 추월 당하는 선수의 인덱스를 찾고 → 해당 인덱스를 기반으로 배열의 값을 변경해주는 코드를 짰었는데 몇 개의 테스트케이스에서 시간초과 발생
  (calling의 길이가 최대 1,000,000이기 때문에 만약 player를 맨 끝에 있는 애로 탐색하여 계속 찾아야 하는 케이스라면 최대 50,000 * 1,000,000번이 된다.)
  
• 따라서 질문하기를 뒤져본 결과, 사전을 이용해야 한다는 힌트를 얻게 되었다. https://school.programmers.co.kr/questions/49719
  
• 사전에 {선수이름 : 인덱스값} 형식으로 저장해준 뒤, 해당 선수이름으로 인덱스 값을 찾고 → 이를 기반으로 순서를 바꿔준다.

What I learned

• tmp 변수를 따로 선언하여 변경되기 이전 값을 저장하고 순서를 바꿔줄 필요 없이, 콤마 하나로 한번에 바꿔줄 수 있었다.

>>> 1
tmp = players[c]
players[c] = players[c-1]
players[c-1] = tmp

>>> 2
players[c-1], players[c] = players[c], players[c-1]