24. 달리기 경주

 

players 의 배열의 원소 위치를 바꾸는데

callings 에서 해당 원소가 나올때마다 인덱스를 왼쪽으로 이동 하게된다. 

 

mumu soe poe kai mine 

 

kai -> mumu soe kai poe mine 

kai -> mumu kai soe poe mine 

mine -> mumu kai soe mine poe

mine -> mumu kai mine soe poe

 

---

1. callings 에서 원소를 하나씩 꺼내온다.

2. players 에서 해당 원소의 위치를 찾는다. 

3. 왼쪽으로 한칸 땡겨준다.

4. callings 의 모든 원소에 대해서 반복한다.

 

---

def solution(players, callings):
    answer = []
    
    for call in callings:
        print(players.index(call))
        
    return answer

 

index 함수를 사용하면 다음과 같이 위치를 인덱스로 알려주게 된다. 

 

 

 

총 4개로 나눌 수 있다 .

앞순위 변동없음 : mumu soe

추월 당하는 : poe

추월 하는 call : kai

뒷순위 변동없음 : mine 

 

순서대로 다음과 같이 나눌 수 있으며 

print(players[:idx-1], [players[idx-1]], [call] ,players[idx+1:])

 

[players[idx-1]], [call] 의 순서를 바꾸게 되면 순위가 바뀌게 된다. 

---

def solution(players, callings):
    answer = []
    
    for call in callings:
        idx = players.index(call)
        
        players = players[:idx-1] + [call] + [players[idx-1]] + players[idx+1:]
        
        answer = players
        
        
    return answer

 

 

---

 

결과는 시간초과로 실패하였다. 

players 의 길이와 callings 의 길이가 매우 길어질 경우 이렇게 되는거 같다. 

최대 5만명의 players 가 100만번 순위가 뒤바뀔수 있다는 제한조건인데.. 

 

 

def solution(players, callings):
    answer = []
    
    for call in callings:
        idx = players.index(call)
        # players = players[:idx-1] + [call] + [players[idx-1]] + players[idx+1:]
        # answer = players

    return answer

 

2줄을 주석처리하고 진행해도 시간 초과가 났다. 

 

def solution(players, callings):
    answer = []
    
    for call in callings:
        len(call)+1

    return answer

 

for 문자체에 대해서는 시간초과가 안나는걸로 보아 callings 에 대한 for 문까지는 진행해도 될거같다. 

index 함수에서 시간초과가 난것으로 생각이되며 다른 방법을 찾아야겠다. 

 

---

슬라이싱이 아닌 바로 원소의 위치를 교환하는 방식으로 변경하였다.

조금 더 빨라지긴 했으나 아직 해결되지 않는다. 

 

def solution(players, callings):
    
    for call in callings:
        idx = players.index(call)       
        players[idx-1], players[idx] = players[idx], players[idx-1]

    return players

 

 

---

 

만약 dic 으로 푼다면 

 

def solution(players, callings):
    dic = {}
    j = 0
    for i in players:
        dic[i] = j
        j += 1
        
    print(dic)
    
    return players

 

---

callings 에서 순위가 바뀌는 target_player 의 현재 rank 를 얻고 그 순위보다 1작은 순위의 pre_player 를 얻어야 된다. 

즉 target 이 추월하려는 사람의 정보는 그 사람보다 순위가 높다는 정보하나밖에 없기 떄문에 이를 활용하기 위해서 dic를 2개 사용하였다.

 

dic = player : 순위

dic2 = 순위 : player 

 

 

 

def solution(players, callings):
    answer = []
    dic = {} # player - 순위
    dic2 = {} # 순위 - player
    j = 0
    for i in players:
        dic[i] = j
        dic2[j] = i
        j += 1
    
    for target_player in callings:
        rank = dic[target_player] # 3
        pre_player = dic2[rank-1] # poe
        
        dic[target_player] , dic[pre_player] = dic[pre_player], dic[target_player]
        dic2[rank] , dic2[rank-1] = dic2[rank-1] , dic2[rank]
    
    # 정렬
    dic2 = dict(sorted(dic2.items()))
    
    for i in dic2:
        answer.append(dic2[i])
    
    return answer

 

 

dictionary 로 조회를 하니 훨씬 빠른 속도가 나오게 되었다.