[Algorithm / 25.03.21] 달리기 경주

1. 문제 설명

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

2. 문제 풀이

import Foundation

func solution(_ players: [String], _ callings:[String]) -> [String] {
    
    var players = players
    
    func swap(_ players: inout [String], _ called: String) {
        if let index = players.firstIndex(of: called), index > 0 {
            let temp = players[index]
            players[index] = players[index-1]
            players[index-1] = temp
        }
    }
    
    for called in callings {
        swap(&players, called)
    }
    
   return players
}

 

일단 이렇게 했는데 다 통과는 되는데 56.3점이 나온다. swap 함수를 써야겠다는 생각은 문제 읽으면서 들었는데 막상 그 인덱스를 어떻게 찾지 싶어서 처음엔 map함수를 썼다가 그러면 어느 변수에 따로 할당을 해주어야 하는데...? 싶어서 어제 배운 inout을 써서 메모리를 조금이나마 덜 쓰도록 하려고 했다. 결국 이러면 index를 찾아야하는데 아직 array같은 컬렉션에 관한 메서드에 익숙치 않아서 인덱스 찾는건 어떻게 하려나 싶어 찾아보았는데, firstIndex를 써야 한다고 한다. 해당 인덱스에 접근해 swap을 쓸 수 있도록 한다. 

모든 경우의 수를 처리해야 하기에 for문을 통해 callings를 전부 순회하며 swap을 돌리고 그 결과로 나오는 players를 반환하도록 했다.

 

클로드에게 로직을 물어보고 다시 구현해보았다.

import Foundation

func solution(_ players: [String], _ callings:[String]) -> [String] {
    guard 2...1000000 ~= callings.count else {
            return []
        }
    
    var players = players
    var indexMap = [String: Int]()
    
    for (index, player) in players.enumerated() {
        indexMap[player] = index
    }
    
    for called in callings {
        
        if let currentIndex = indexMap[called], currentIndex > 0 {
            var prevIndex = currentIndex - 1
            var prevValue = players[prevIndex]
            
            players[prevIndex] = called
            players[currentIndex] = prevValue
            
            indexMap[prevValue] = currentIndex
            indexMap[called] = prevIndex
        }
        
    }
    
   return players
}

 

기존 풀이법에선 swap이 호출될 때마다 firstIndex(of: )로 배열을 처음부터 순회한다(O(n)). 이를 callings 배열의 모든 요소에 대해 반복하기 때문에, 또 동시에 배열에서 요소를 찾는 거기 때문에 firstIndex(of:)를 쓰며 선형 탐색을 한다. (배열도 생성 시 O(n))

 

새 방법에선 초기 인덱스 맵 생성 하는 데에 O(n)이, 각 호출 처리엔 O(1) * m = O(m)의 시간복잡도를 가지고, 딕셔너리를 사용하여 O(1)에 플레이어의 현재 인덱스를 얻는다. 위치 교환 후 딕셔너리도 함께 업데이트해 인덱스 정보를 최신 상태로 유지한다.

 

시간 복잡도만 두고 보면, 배열만 사용할 경우 O(n) + O(m*n)이 되고 딕셔너리의 경우 O(n) + O(m)의 차이점이 있다.

 

결국 큰 입력에서 두 번째 방법이 훨씬 효율적이다. 첫 번째 방법은 매번 배열을 순회해야 하기에 데이터가 클수록 성능이 저하되는데, 두 번째 방법은 초기 설정 후 상수 시간에 위치를 교환할 수 있어 훨씬 빠르다.

 

---

문제 자체는 풀었는데 일부 케이스에서 실패하는 경험을 오늘 처음 해봤다. 어디가 문젠지 견문이 없어 알지 못했고 이를 AI를 통해 문제를 짚어보았는데, 팀원분들이 일부 메서드의 시간 복잡도가 높아서 다른 방법을 이용한다는 대화가 생각났다.