[프로그래머스] Lv. 1 - 달리기 경주

제목: Lv. 1 - 달리기 경주

시간: 30분

 

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

프로그래머스

 

문제가 아주 직관적이었다.

 

문제를 본 느낌대로 일단 코딩을 해봤는데, 역시나 시간초과가 생겼다.

 

import Foundation

func solution(_ players:[String], _ callings:[String]) -> [String] {
    
    var result = players
    
    for i in callings {
        var index = result.firstIndex(of: i)!
        
        var tmp = result[index]
        result[index] = result[index-1] 
        result [index-1] = tmp
    }

    return result
}

 

입력으로 들어오는 배열의 길이가 100만까지고, 현재 등수를 나타내는 배열은 5만으로 

중첩해서 탐색하게 된다면 아주 시간이 오래 걸릴 수 밖에 없었다.

 

그래서 시간 복잡도 방법을 어떻게 줄일지 고민하고 찾아봤다.

 

안쓴지 꽤 돼서 잊고 있었던 Dictionary로 하면 시간 복잡도를 줄일 수 있다는 것을 알게되었다.

 

일반적으로 배열의 선형 탐색은 O(n)인 반면, Dictionary는 해시 테이블 구조로 만들어져 있어서 엄청 빠르게 탐색할 수 있다.

 

import Foundation

func solution(_ players:[String], _ callings:[String]) -> [String] {
    var dict: [String: Int] = [String: Int]()
    var result = players
    
    result.enumerated().forEach { (index, value) in
        dict[value] = index
    }
    
    for i in callings {
        var targetIndex = dict[i]!                  // 불린 선수 등수
        var frontTargetIndex = targetIndex - 1      // 불린 선수 앞 등수
        
        var target = i                              // 불린 선수
        var frontTarget = result[targetIndex - 1]   // 불린 선수 앞 이름
        
        dict[target]! -= 1
        dict[frontTarget]! += 1
        
        result.swapAt(targetIndex, frontTargetIndex)
    }

    return result
}

 

또 찾아보면서 배열의 swapAt 메소드를 알게 되었는데, 첫 번째 코드에서 나왔던 템프 어쩌구 하는 과정을 줄일 수 있어서 좋았다.

 

정리

1. 키 값 기반으로 한 탐색할 때는 Dictionary

2. 유용한 메소드 익히기 SwapAt