프로그래머스 Lv1. 달리기 경주

https://school.programmers.co.kr/learn/courses/30/lessons/178871?language=python3 

프로그래머스

문제 자연수의 집합이자 길이가 같은 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱한 값의 누적이 최소가 되는 값 리턴

 

내 답안

def solution(players, callings):
    for i in range(len(callings)):
        if callings[i] in players:
            num = players.index(callings[i])
            players[num], players[num-1] = players[num-1], players[num]
        
    return players

위 코드로는 8~16번 예시에서 시간 복잡도 초과로 오류가 난다. list에서 value로 index에 바로 접근할 수 없으니까 .index를 활용한 것이 시간복잡도를 무지하게 늘린 모양이었다. 

이 문제를 해결하기 위해서는 map 함수 등을 활용해볼 수 있겠는데, 나는 enumerate와 dict를 활용해서 등수, 이름을 따로 하나의 dict에 저장하고 거기로 접근하는 방법을 이용했다. 

 

다시 풀어본 답안 

def solution(players, callings):
    rank = dict()
    for i, v in enumerate(players):
        rank[v] = i
        
    for p in callings:
        pre, post = rank[p] - 1, rank[p]
        rank[players[pre]] = post
        rank[players[post]] = pre
        
        players[pre], players[post] = players[post], players[pre]
        
    return players

dict 자료형에서는 value 값으로 index에 접근할 수 있으므로, pre와 post 변수에 각각의 index를 저장해준다. 

그러면 list인 players의 value도 pre, post에 저장된 index로 호출할 수 있게 된다.