[프로그래머스]Lv1. 달리기 경주(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/178871

프로그래머스

 

문제 접근

 

1차 생각

이중 반복문을 돌면서 부른 이름을 리스트를 돌면서 처음부터 찾고, players 리스트 자체에서 swap 시킬까?

 

2차 생각 

(1) 딕셔너리에 선수들의 순서를 저장해서 이름이 불리면 그 이름에 해당하는 순서를 찾고 players 리스트에 반영

(2) 반영한 순서를 다시 선수들의 순서가 저장된 딕셔너리에 반영 

 

2차 생각으로 접근을 시작했다. => 딕셔너리를 사용하면 각 호출마다 시간 복잡도가 O(1)이므로 효율적 

우선 names라는 빈 딕셔너리를 선언한 후 {이름: 순서} 꼴로 저장 왜냐면 callings라는 배열에 담긴게 이름이니까 {순서: 이름}은 맞지 않다고 생각했다. 

 

<시간 복잡도>

 O(N)

 

코드 

def solution(players, callings):
    names = {}
    
    # 어떻게 할당할까? {이름: 순서}, {순서: 이름} => 전자 선택 
    
    for i, player in enumerate(players):
        names[player] = i   
    
    for call in callings:
        idx = names[call]   # 부른 이름의 값을 찾자 
        
        players[idx], players[idx-1] = players[idx-1], players[idx] # players리스트에서 순서를 바꾸자 
        
        # 바꾼 순서를 딕셔너리에 반영해 순서 재저장 
        names[players[idx]] = idx 
        names[players[idx-1]] = idx-1
        
    return players