프로그래머스 ) 달리기 경주

 알고리즘 공부 시작한 이유 

취업을 위해서 알고리즘 공부를 꾸준히 해야 함을 느끼고 있다. 특히나,, 요즘 알고리즘 수업을 듣고 있는데 교수님이 너무 잘 가르쳐주셔서 군침이 싸악 도는 중이다. 파이썬으로 학교 수업을 해서 파이썬으로 알고리즘을 공부해야 하나 했는데, iOS 개발자가 되기로 했고 알고리즘을 잘 하기 위해서는 언어에도 친숙해질 필요가 있음을 느꼈기 때문에, swift를 선택하게 되었다.

재작년에는 알고리즘이 조금 멀게만 느껴졌었고, 작년에는 좀 더 잘하고 싶은 마음이 급급했던 것 같다. 그래서 올해는 다시 처음부터 다시 배운다는 느낌으로 차근차근 알고리즘 공부를 해볼 생각이다. 

지금 내가 느낀 문제는 알고리즘 수업 덕분에 머릿속에는 그래도 약간 어떻게 해야할지에 대해 알고리즘 수도 코드가 생각나는데, 언어에 익숙하지 않아서 허비하는 시간이 많았다. ( swift를 선택한 이유이기도 하다. ) 

프로그래머스 레벨 1부터 차근차근 해보자. 화이팅 !

 달리기 경주 문제 

프로그래머스

 

 1차 실패 : 시간 초과 

처음에는 배열로 문제를 풀려고 했다. 하지만 players가 n개, calling이 m개라고 할때 최악의 경우 O(n+m)의 시간복잡도를 가지기 때문에 시간초과가 걸렸다.

그래서 dictionary라고 풀어야 함을 직감했다. 나는 다음과 같이 key값이 다른 두 딕셔너리를 만들었다. dictionaryName만 있는 경우 A라는 사람이 들어왔을 때 A 앞에 있는 B라는 사람을 찾아야 하는데, 이때 B를 찾기 위해서 또 dictionaryName의 value를 순차적으로 돌며 확인해야 하기 때문에 시간복잡도가 배열로 할 때랑 비슷할 거라 생각했기 때문이다. 

dictionaryName = ["mine": 4, "soe": 1, "poe": 2, "mumu": 0, "kai": 3]
dictionaryValue = [3: "kai", 4: "mine", 1: "soe", 0: "mumu", 2: "poe"]

 

 알게 된 것 

Dictionary init 방법에 대해 공부할 수 있는 시간이었다. ( 아래 링크 참고 )

Swift) Dictionary 초기화 방법

init(uniqueKeysWithValues:) 

그 중에 uniqueKeysWithValues을 이용해서 문제를 풀었다.

Dictionary(uniqueKeysWithValues: zip(key,value 튜플))는 array1과 array2를 1:1 mapping을 해서 dictionary로 만들때 사용한다.

let digitWords = ["one", "two", "three", "four", "five"]
let indexs = Array(1...5)
let wordToValue = Dictionary(uniqueKeysWithValues: zip(digitWords, indexs))
// let wordToValue = Dictionary(uniqueKeysWithValues: zip(digitWords, 1...5))

print(wordToValue) //  "["three": 3, "four": 4, "five": 5, "one": 1, "two": 2]"

 

 결과 

다른 사람들 코드를 보니까 dictionaryName만 만들어서 해결하기도 했길래 생각을 해봤다.. 왜지..?

( players가 n개, calling이 m개라 가정 )

calling에서 불려진 이름이 A일 때 dictionaryName에서 A 앞의 사람을 찾아야 한다고 생각했었어서 이때 dictionaryName에서 (A의 value -1)을 찾으려면 또 O(n)이 걸려서 또 전체 시간 복잡도가 O( n+m )이 될 거라 생각했다.

근데,, ㅋㅋ 코드를 보니 player 배열에서 (A의 value -1)을 찾을 수 있었다.. ㅠㅠ 편협한 생각 하지 말자..

import Foundation

func solution(_ players:[String], _ callings:[String]) -> [String] {
    let names = players
    let values = Array(0..<players.count)
    var dictionaryName = Dictionary(uniqueKeysWithValues: zip(names, values))
    var dictionaryValue = Dictionary(uniqueKeysWithValues: zip(values, names))
    
    for name in callings {
        // 이름이 불리면 해당 이름의 등수를 앞 사람이랑 교환함
        let value = dictionaryName[name]!
        let pre_value = value - 1
        let pre_name = dictionaryValue[pre_value]!
        
        dictionaryName[name] = pre_value
        dictionaryName[pre_name] = value

        dictionaryValue[value] = pre_name
        dictionaryValue[pre_value] = name
    }

    let answer = dictionaryName.sorted(by: { $0.value < $1.value}).map { $0.key }

    return answer
}

그래서 dictionaryName하나만 만들어서 짠 코드

func solution(_ players:[String], _ callings:[String]) -> [String] {
    var answer = players
    var dictionaryName: [String : Int] = Dictionary(uniqueKeysWithValues: zip(players, 0..<players.count))
    callings.forEach { player in
        let rank = dictionaryName[player]!
        let otherPlayer = answer[rank - 1]
        answer.swapAt(rank, rank - 1)
        dictionaryName[player]! -= 1
        dictionaryName[otherPlayer]! += 1
    }
    return answer
}