[Swift 알고리즘] 프로그래머스 154538 (숫자 변환하기)

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

프로그래머스

 

 

해결 방법

BottomUP으로 했는데 시간초과 나서 TopDown 방식으로 고쳐봤습니다. 제 생각에는 BottomUp도 문제 없을 것 같습니다.

1. Queue를 쓰기 힘드니 ind를 통해 Queue를 구현하wk.

    - removeFirst()의 경우 timeComplexity의 경우O(n)이다.

2. Set.contains의 경우 complexity가 O(n)이기에 hash를 이용하자

 

 

import Foundation

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    var queue: [[Int]] = [[y, 0]] //queue는 [현재 값, 얼마나 지나왔는지]
    var hash: [Int: Int] = [y:0]
    var tempInd = 0
    while tempInd < queue.count && hash[x] == nil {
        let node = queue[tempInd] //[현재 값, 얼마나 지났는지]
        tempInd += 1
        if node[0] - n >= x && hash[node[0] - n] == nil{
            hash[node[0] - n] = node[1] + 1
            queue.append([node[0] - n, node[1] + 1])
        }
        if node[0] % 2 == 0 && hash[node[0] / 2] == nil {
            hash[node[0] / 2] = node[1] + 1
            queue.append([node[0] / 2, node[1] + 1])
        }
        if node[0] % 3 == 0 && hash[node[0] / 3] == nil {
            hash[node[0] / 3] = node[1] + 1
            queue.append([node[0] / 3, node[1] + 1])
        }
    }
    return hash[x] == nil ? -1 : hash[x]!
}

 

 

후기 : 

해결 하고 보니 set의 자료구조가 더 깔끔한 것 같네요