[파이썬]프로그래머스 Lv.1 달리기경주

✅ 코드

def solution(players, callings):
    players_dict = {player: idx for idx, player in enumerate(players)}
    for name in callings:
        idx = players_dict[name]
        front = players[idx - 1]
        players[idx - 1], players[idx] = players[idx], players[idx - 1]
        players_dict[name], players_dict[front] = idx - 1, idx
    return players

입력값의 제한은 다음과 같습니다.

• 5 <= players 배열의 길이 <= 50,000
• 2 <= callings 배열의 길이 <= 1,000,000

첫 번째 풀이는 시간 초과 문제가 있었습니다.

callings 배열에 대해 반복문을 돌리고 매 시행마다 리스트의 index 함수를 사용했기 때문입니다.

시간복잡도를 계산하면 50,000 * 1,000,000으로 해당 값은 1억을 초과합니다.

따라서 시간이 초과하는 것이었습니다.

 

두 번째 풀이로 딕셔너리를 사용하는 풀이법을 떠올렸습니다.

딕셔너리에서 특정한 값을 검색하는 데 소요되는 시간복잡도는 O(1)입니다.

이는 index 함수를 사용한 경우보다 훨씬 빠른 수치입니다.

players 배열에 있는 각 선수들의 이름을 딕셔너리의 키로, 각 선수들의 인덱스 값을 딕셔너리의 값으로 설정하기 위해 enumerate 함수와 딕셔너리 컴프리헨션을 사용했습니다.