[programmers]달리기 경주

import Foundation

func change(_ CurrentPlayers: [String], _ forwardPlayer: String) -> [String]{
    var currentPlayers = CurrentPlayers
    for rank in 0...currentPlayers.count{
        if(currentPlayers[rank-1] == forwardPlayer){
            var temp = currentPlayers[rank-2]
            currentPlayers[rank-2] = forwardPlayer
            currentPlayers[rank-1] = temp
        }
    }
    return currentPlayers
}

func solution(_ players:[String], _ callings:[String]) -> [String] {
    var result: [String] = players
    
    for idx in 0..<callings.count{
        result = change(result, callings[idx])
    }
    
    return result
}

 

첫번째 문제 접근

change라는 함수를 생성하여 현재 순위의 정보를 가지고 있는 players 배열을 입력받고 호명 당한 말을 입력을 받아 반복문 통해 배열을 순회하고 호명된 말이 조건을 통해 알아내 앞에 달리고 있는 말(index(호명된 말) - 1)을 이용해 자리를 바꾸는 함수를 짰습니다.

 

그리고 이 함수를 호명된 말을 저장한 말들을 저장한 배열의 크기만큼 change함수를 반복하여 순위를 재배치하는 코드를 짰습니다.

문제점

players에서 호명된 말을 찾기위해 반복(n)과 호명한 횟수(m) 반복하여 순위를 재배치했기 때문에 시간복잡도 O(n*m)이 되어 버렸다.

 

해결

반복을 줄이고자 players에서 호명된 말을 찾기 위한 방법으로 딕셔너리 자료형을 이용해서 players 배열에서 호명된 말을 찾기 위한 반복을 없애는 방법을 채택하였습니다.

import Foundation

func solution(_ players:[String], _ callings:[String]) -> [String] {
    var player = players
    var call = callings
    var rank = [String : Int]()
    
    for i in 0 ..< player.count{
        rank[player[i]] = i
    }
    
    for i in 0 ..< call.count{
        var idx = rank[call[i]]!
        var temp = player[idx - 1]
        player[idx - 1] = player[idx]
        player[idx] = temp
        rank[call[i]]! -= 1
        rank[temp]! += 1
    }
    return player
}

입력으로 주어진 말의 이름(String)과 등수(Int)를 딕셔너리에 저장을하고 호명된 말을 key값으로 사용해 등수를 알아내고 알아낸 등수를 가지고 앞에 달리고 있는 말과 호명된 말의 등수를 바꾸는 형식으로 코드를 짰습니다.

Reference

https://jenikeju.tistory.com/34

달리기 경주 Swift