[Swift][프로그래머스] 달리기 경주

프로그래머스: 달리기 경주 - 문제링크

---

기존 코드

import Foundation

func solution(_ players:[String], _ callings:[String]) -> Any {
    var newRun = players
    for i in callings {
        let idx = newRun.firstIndex(of:i)!
        if idx == 0 {
            continue
        }
        newRun.remove(at:idx)
        newRun.insert(i, at:idx-1)
    }
    return newRun
}

시간초과 날걸 예상하긴 했지만 걍 써봤다 ㅋ
remove at:, insert at: 등을 사용하면 영향받는 배열 전체가 앞으로 또는 뒤로 이동해야 해서 최악의 경우 시간복잡도는 O(n)이 되고, 배열의 길이가 길거나 callings의 count가 커지면 최악의 경우 O(k*n)의 시간복잡도를 갖게 된다.

따라서 코드가 복잡해지더라도 인덱스를 기반으로 접근하여 해결해야 한다.

수정 코드

import Foundation

func solution(_ players:[String], _ callings:[String]) -> [String] {
    var runDict = [String:Int]()
    var newRun = players
    newRun.enumerated().forEach { (idx, i) in runDict[i] = idx }
    
    
    for i in callings {
        let newRank = runDict[i]! - 1
        if newRank >= 0 {
            (newRun[newRank], newRun[newRank+1]) = (i, newRun[newRank])
            (runDict[i], runDict[newRun[newRank+1]]) = (newRank, newRank + 1)
        }
    }
    return newRun
}

딕셔너리를 활용해 배열 인덱스에 접근하여 값을 조정했다.

swapAt

풀긴 풀었는데 모범답안을 보니 swapAt이라는 고상한 메서드를 사용하고 있었다. swapAt은 배열에서 인덱스에 접근해 두 값을 바꿔주는 메서드이다. 시간복잡도는 둘 다 O(1)로 효율적이지만, 튜플 교환보다 코드 가독성이 좋아보이니 한번 사용해보도록 하겠다.

import Foundation

func solution(_ players:[String], _ callings:[String]) -> [String] {
    var runDict = [String:Int]()
    var newRun = players
    newRun.enumerated().forEach { (idx, i) in runDict[i] = idx }
    
    
    for i in callings {
        let newRank = runDict[i]! - 1
        let playerLose = newRun[newRank] // 해당 상수 새로 생성
        if newRank >= 0 {
            newRun.swapAt(newRank, newRank+1) //swapAt 사용
            (runDict[i], runDict[playerLose]) = (newRank, newRank + 1)
        }
    }
    return newRun
}