[Swift/프로그래머스] 숫자 변환하기 ( 그리디 )

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

프로그래머스

 

이런 유형의 문제를 전에도 본적이 있다.

 

그때는 더하기 뺴기 나누기 곱 4가지 경우였는데 이번에는 3가지의 연산만 처리하면 됐다.

 

문제 설명

 

자연수 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

 

첫번째 풀이

import Foundation

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    
    if y < x {
        return -1
    }
    // x와 y가 같으면 연산 필요 없음
    if x == y {
        return 0
    }

     var visited = Set<Int>()
    
    var queue = [(Int, Int)]()
    queue.append((x, 0)) // 현재숫자와 연산 횟수
    visited.insert(x)
    
    while !queue.isEmpty {
        let (current, count) = queue.removeFirst()
        
        // 세 가지 연산 수행
        let operations = [
            current + n,    // 더하기 n
            current * 2,    // 곱하기 2
            current * 3     // 곱하기 3
        ]
        
         for next in operations {
            // y보다 크면 스킵
            if next > y {
                continue
            }
            
            // y에 도달하면 현재까지의 연산 횟수 + 1 반환
            if next == y {
                return count + 1
            }
            
            // 이미 방문한 숫자면 스킵
            if visited.contains(next) {
                continue
            }
            
            // 큐에 추가하고 방문 처리
            queue.append((next, count + 1))
            visited.insert(next)
        }
        
    }
    
    return -1
}

 

나누기나 빼기가 없기때문애 단순히 x 값이 y 보다 커졌으면 continue를 하는 방식으로 해결해보았다.

 

하지만 테케 9,10에서 시간초과가 발생했다.

 

정답

import Foundation

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    // y가 x보다 작으면 변환 불가능
    if y < x { return -1 }
    if x == y { return 0 }
    
    // dp[i]는 i를 만들기 위한 최소 연산 횟수
    var dp = [Int](repeating: Int.max, count: y + 1)
    dp[x] = 0 // 시작점
    
    // x부터 y까지 순차적으로 처리
    for i in x...y {
        // 현재 위치에 도달할 수 없는 경우 스킵
        if dp[i] == Int.max { continue }
        
        // 각 연산 결과가 y 이하인 경우에만 처리
        if i + n <= y {
            dp[i + n] = min(dp[i + n], dp[i] + 1)
        }
        if i * 2 <= y {
            dp[i * 2] = min(dp[i * 2], dp[i] + 1)
        }
        if i * 3 <= y {
            dp[i * 3] = min(dp[i * 3], dp[i] + 1)
        }
    }
    
    // y에 도달할 수 없는 경우 -1 반환
    return dp[y] == Int.max ? -1 : dp[y]
}