[알고리즘] 프로그래머스 - 달리기 경주

달리기 경주

 

1. 구해야 하는 것
    # calligns가 다 끝난 뒤 배열
2. 1을 구하기 위해 필요한 것
    # callings의 원소마다 players의 해당하는 값을 옮기기
        # calling과 동일한 players의 원소와 그 앞의 원소 위치변경   
            # swap을 통해 바꾸기
3. 그 외 고려해야 할 사항
    # 5 ≤ players의 길이 ≤ 50,000
    # 2 ≤ callings의 길이 ≤ 1,000,000
    # callings안에서 players.index()를 한번만 호출해도 500억번 연산을 시작
    # players를 딕셔너리로 바꿔서 시간 복잡도 줄이기

 

 

1. players를 index와 함께 딕셔너리에 enumerate를 사용해 넣는다.

2. callings의 i에 해당하는 값을 딕셔너리에서 찾아서 변수에 할당.

3. 현재 플레이어를 2.에서 찾은 값을 이용해 인덱스로 구한다.

4. 그 앞 선수를 마찬가지로 구해준다.

5. 딕셔너리에서 현재 선수의 등수를 1 줄이고, 앞 선수의 등수를 1늘린다.

6. 두 선수의 위치를 리스트에서도 바꿔준다.

def solution(players, callings):
    players_dict = {}
    for i, j in enumerate(players):
        players_dict[j] = i
    for i in callings:
        a = players_dict[i]
        cur = players[a]
        pre = players[a-1]
        players_dict[cur] -= 1
        players_dict[pre] += 1

        players[a] = players[a-1]
        players[a-1] = cur
    answer = players
    return answer