Algorithm / 숫자 변환하기

문제

프로그래머스 / 숫자 변환하기

1) 문제 풀이

func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
    if x == y { return 0 }
    var answer = -1
    
    func bfs(_ currentSum: Int, _ count: Int) {
        if currentSum == y {
            if answer == -1 { answer = Int.max }
            answer = min(answer, count)
            return
        }
        
        if currentSum > y {
            return
        }
        
        bfs(currentSum + n, count + 1)
        bfs(currentSum * 2, count + 1)
        bfs(currentSum * 3, count + 1)
    }
    
    bfs(x, 0)
        
    return answer
}

결과

2) 코드 개선

⚠️ 문제점 분석

• 중복 호출:
  • currentSum을 통해 답을 도출하기 때문에 모든 경로를 탐색하게 됨
  • 이는 불필요한 연산(이미 최저값을 찾은 후에도 계속 찾음)이 기하급수적으로 증가하여 비효율적
• 깊은 재귀 호출(스택 오버플로우 위험성):
  • 예: x = 1, y = 1000000, n = 1인 경우 +n만 해도 백만 번 호출
  • 재귀호출이 너무 깊어져 스택 오버플로우 발생 가능성
• DFS는 최소 횟수 찾기에 비효율적:
  • 현재 함수명을 bfs로 했으나 실제 동작 방식은 dfs
  • dfs는 최단 거리 찾기에는 비효율적이며, bfs가 더 적합함

✅ 코드 개선점

• BFS로 구현
• visited를 활용하여 중복 체크
• 너무 큰 숫자는 탐색하지 않기

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

    var visited = Set<Int>()
    var queue: [(Int, Int)] = [(x, 0)]

    while !queue.isEmpty {
        let (current, count) = queue.removeFirst()

        for next in [current + n, current * 2, current * 3] {
            if next > y || visited.contains(next) { continue }
            if next == y { return count + 1 }

            visited.insert(next)
            queue.append((next, count + 1))
        }
    }

    return -1
}

결과