Algorithm / 달리기 경주

𝕮𝖗𝖔𝖎𝖘𝖘𝖆𝖓𝖙·2025년 5월 29일

알고리즘 코드카타

목록 보기

25/59

1) 문제

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

2) 문제 풀이

func solution(_ players:[String], _ callings:[String]) -> [String] {
    var currentRanks = players
    
    for player in callings {
        if let index = currentRanks.firstIndex(of: player) {
            currentRanks.swapAt(index, index - 1)
        }
    }
    
    return currentRanks
}

결과

3) 코드 개선

1️⃣ 문제점

firstIndex(of:)의 반복 호출 → O(n) 시간 복잡도
이는 callings.count만큼 반복 → 전체 시간 복잡도 = O(n*m)
이 때문에 시간 초과 발생

2️⃣ 개선 전략

Dictionary<String, Int>를 병행 사용하여 해결
시간 복잡도: O(n) → O(1)

import Foundation

func solution(_ players: [String], _ callings: [String]) -> [String] {
    var currentRanks = players
    var nameToIndex = [String: Int]()
    
    // 초기 맵 구성
    for (index, name) in players.enumerated() {
        nameToIndex[name] = index
    }
    
    for name in callings {
        guard let currentIndex = nameToIndex[name], currentIndex > 0 else { continue }
        
        let frontIndex = currentIndex - 1
        let frontPlayer = currentRanks[frontIndex]
        
        // 순서 바꾸기
        currentRanks.swapAt(currentIndex, frontIndex)
        
        // 인덱스 맵도 함께 업데이트
        nameToIndex[name] = frontIndex
        nameToIndex[frontPlayer] = currentIndex
    }
    
    return currentRanks
}