[프로그래머스] 숫자 변환하기 Swift

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

---

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

---

내가 푼 풀이

- 모든 경우의 수를 구하는 방식으로 중복을 제거하는 Set 안에 연산한 결과를 전부 넣었다.

- 넣을 수 없는경우 -1을 출력한다.

- dp방법도 있는데 나중에 풀어봐야겠다..

 

 

import Foundation

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    var numSet = Set([x])
    var result = 0
    
    while true {
        var addSet = Set<Int>()
        if numSet.contains(y) {
            return result
        }
        for i in numSet {
            if i+n <= y {
                addSet.insert(i+n)
            }
            if i*2 <= y {
                addSet.insert(i*2)
            }
            if i*3 <= y {
                addSet.insert(i*3)
            }
        }
        numSet  = addSet
        result += 1
        if numSet.isEmpty {
            break
        }
    }

    return -1
}

 

 

< DP 풀이>

Array의 크기: y+1, 배열의 원소를 모두 Int의 최댓값으로 선언

시작점 x 의 arr[x] = 0

세가지 연산 x+n , x*2 , x*3 수행후 y보다 같거나 작으면 

•  x+n <= y : arr[x+n] = min(arr[x]+1, arr[x+n])
•  x * 2 <= y : arr[x+n] = min(arr[x]+1, arr[x+n])
•  x * 3 <= y : arr[x+n] = min(arr[x]+1, arr[x+n])

최소 연산횟수를 구해야하므로 min 적용한다.

결과: arr[y] : 만약 세가지 연산으로 arr[y] 의 값을 변경하지 못했다면 arr[y] = Int.max

 

import Foundation

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    var arr = Array(repeating: Int.max, count: y+1)
    arr[x] = 0
    
    for i in x...y where arr[i] != Int.max {
        if i+n <= y {
            arr[i+n] = min(arr[i] + 1, arr[i+n])
        }
        if i*2 <= y {
            arr[i*2] = min(arr[i] + 1, arr[i*2])
        }
        if i*3 <= y {
            arr[i*3] = min(arr[i] + 1, arr[i*3])
        }
    }
    if arr[y] == Int.max {
        return -1
    } else {
        return arr[y]
    }
}