99클럽 코테 스터디 26/99일차 TIL #달리기 경주(미들러)

 

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

프로그래머스

 

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.
선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

 

자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름 부름

해당 이름이 불리면 index를 한 칸 앞으로 당기기
1등은 불리지 않음

def solution(players, callings):
    
    
    for calling in callings:
        idx = players.index(calling)
        players.remove(calling)
        players.insert(idx-1, calling)        
        
    return players

 

시간 초과가 발생하는 이유는 players.index(calling)와 같은 리스트 연산이 호출될 때마다 리스트를 순회하기 때문입니다. index, remove, insert 같은 연산은 리스트의 길이에 비례하는 O(n)의 시간 복잡도를 가지기 때문에, 호출이 많아지면 전체 연산이 매우 느려질 수 있습니다.

이를 해결하기 위해 더 효율적인 방법을 사용해야 합니다. 여기서는 리스트와 딕셔너리를 함께 사용하여 문제를 해결하는 방법을 설명하겠습니다.

개선된 접근 방법

1. 플레이어의 위치를 저장하는 딕셔너리 사용: 각 플레이어의 현재 인덱스를 기록하는 딕셔너리를 생성합니다. 이렇게 하면 특정 플레이어의 위치를 O(1) 시간 복잡도로 찾을 수 있습니다.
2. 인덱스 업데이트: 호출된 플레이어와 그 앞에 있는 플레이어의 위치를 서로 바꿉니다.

 

 

def solution(players, callings):
   
    
    for calling in callings:
    
        idx = players.index(calling)

        players[idx], players[idx-1] = players[idx-1], players[idx]

    
    return players

리스트에서 index를 찾는 것 역시 O(n)의 연산 복잡도를 가지기 때문에 앞에 방식과 동일한 O(n)이므로 동일하게 시간초과 발생.

결국 여기서 남은언 index를 list의 함수를 쓰는 것이 아닌 다른 방법을 써야한다는 것.

그 중 가장 쉬운 방법이 dictionary를 사용하는 것이다.

def solution(players, callings):

    position = {player:i for i, player in enumerate(players)}
    
    for calling in callings:
        
        idx = position[calling]
        # players[idx]: current player 
        # players[idx-1]: ahead player 
        
        # players[idx]: ahead player 
        # players[idx-1]: current player 
        players[idx], players[idx-1] = players[idx-1], players[idx]
        
        # current player에 ahead player의 idx로 변경
        position[players[idx]] = idx
        # ahead player에 current player의 idx로 변경
        position[players[idx-1]] = idx-1
    
    
    return players

정확성 테스트

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.04ms, 10.3MB)
테스트 4 〉	통과 (0.29ms, 10.1MB)
테스트 5 〉	통과 (1.74ms, 10.6MB)
테스트 6 〉	통과 (5.89ms, 10.9MB)
테스트 7 〉	통과 (34.22ms, 14.3MB)
테스트 8 〉	통과 (52.48ms, 18.8MB)
테스트 9 〉	통과 (94.79ms, 27.8MB)
테스트 10 〉	통과 (277.24ms, 56.7MB)
테스트 11 〉	통과 (563.33ms, 91.6MB)
테스트 12 〉	통과 (552.90ms, 91.6MB)
테스트 13 〉	통과 (616.09ms, 91.5MB)
테스트 14 〉	통과 (0.01ms, 10.2MB)
테스트 15 〉	통과 (0.01ms, 10.3MB)
테스트 16 〉	통과 (0.01ms, 10MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0