[Algorithm] 숫자 변환하기

[hwangJi-dev]

💬 문제

[코딩테스트 연습 - 숫자 변환하기](https://school.programmers.co.kr/learn/courses/30/lessons/154538)

💬 Idea

첫번째 아이디어

재귀함수를 사용하여 x + n, x * 2, x * 3의 연산을 반복 수행한 후 최소 연산 횟수를 구하자

→ y값이 커지고, n의 값이 작아진다면 수행 시간이 기하급수적으로 늘어나게 되며 결국 시간초과를 초래한다.

두번째 아이디어

동적 계획법 (DP)을 사용하여 풀이한다.

→ 이미 한 번 푼 문제는 그 결과를 저장해 놓았다가 나중에 동일한 문제를 풀어야 할 대 이미 저장한 값을 반환하기 때문에 중복되는 연산을 할 필요가 없어진다!

💬 풀이

실패한 풀이

정확성 (50/100) / 시간초과 발생

import Foundation

var minimum = 0

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    if x == y {
        return 0
    }
    dfs(x, y, n, 0)
    return minimum
}

func dfs(_ x: Int, _ y: Int, _ n: Int, _ sum: Int) {
    if x == y {
        if minimum != 0 {
            minimum = minimum > sum ? sum : minimum
        } else {
            minimum = sum
        }
        return
    }
    
    if x > y {
        if minimum == 0 {
            minimum = -1
        }
        return
    }
    
    dfs(x + n, y, n, sum + 1)
    dfs(x * 2, y, n, sum + 1)
    dfs(x * 3, y, n, sum + 1)
}

성공 풀이

func solution(x:Int, y:Int, n:Int) -> Int {
    if x == y {
        return 0
    }
    
    var dp: [Int: Int] = [x: 0]
    var data = [x]
    
    while data.count != 0 {
        var calResult: [Int] = []
        
        for d in data {
            // d에 n을 더하고, 2를 곱하고, 3을 곱하는 연산을 각각 수행한다.
            for c in [d + n, d * 2, d * 3] {
                // 연산 결과가 y보다 크거나 이미 연산된 값이라면 반복문을 탈출한다.
                if (c > y || dp[c] != nil) {
                    continue
                }
                // 연산 결과가 y값과 같다면 1을 더한 값을 도출한다.
                if c == y {
                    return dp[d]! + 1
                }
                // 메모리에 c의 연산 횟수를 기록한다
                dp[c] = dp[d]! + 1
                calResult.append(c)
            }
        }
        
        //  data에 다음 연산 비교군을 할당한다.
        data = calResult
    }
    
    return -1
}