[프로그래머스 Lv.2] 숫자 변환하기 (Kotlin)

문제 링크

처음엔 다음과 같이 dfs로 접근하여 풀려고 했다.

class Solution {
    
    lateinit var ans: ArrayList<Int>
    
    fun solution(x: Int, y: Int, n: Int): Int {
        ans = arrayListOf()
        
        dfs(x, y, n, 0)
        
        if (ans.isEmpty()) {
            return -1
        } else {        
            return ans.sorted().first()
        }
    }
    
    fun dfs(x: Int, y: Int, n: Int, depth: Int) {
        if (x > y) return
        if (x == y) {
            ans.add(depth)
            return
        }
    
        dfs(x + n, y, n, depth + 1) // n 더하거나
        dfs(x * 2, y, n, depth + 1) // 2 곱하거나
        dfs(x * 3, y, n, depth + 1) // 3 곱하거나
    }
}

그러나 자꾸 시간초과가 났다.

그림을 그려보니 당연한 결과였다.
조건을 만족하는 depth가 최소일 때, 반복문을 빠져나오면 되는데,
dfs 알고리즘으로 접근한다면, 불필요한 경우까지 모두 검사하기 때문이다.

따라서 이 문제는 bfs 알고리즘으로 접근해야 한다.
bfs를 돌리면서, 추가적으로 BooleanArray 방문배열을 선언하여 체크할려고 했으나,
1,000,000이 여러번 곱해지고 더해지면서 배열의 크기가 쓸데없이 커져 메모리 초과가 났기 때문에 방문 체크는 Int 타입의 key와 Boolean value를 갖는 해쉬맵으로 접근하여 풀었다.

문제를 해결한 코드는 아래와 같다.

import java.util.*

class Solution {
    
    lateinit var ans: ArrayList<Int>
    lateinit var q : Queue<Pair<Int, Int>>
    lateinit var visited: HashMap<Int, Boolean>
    
    fun solution(x: Int, y: Int, n: Int): Int {
        ans = arrayListOf()
        q = LinkedList()
        visited = hashMapOf()
        
        bfs(x, y, n, 0)
        
        println(ans.toString())
        
        if (ans.isEmpty()) {
            return -1
        } else {        
            return ans.first()
        }
    }
    
    fun bfs(x: Int, y: Int, n: Int, depth: Int) {
        q.add(Pair(x, depth))
        
        while (q.isNotEmpty()) {
            val node = q.poll()
            
            if (node.first > y) continue
            if (node.first == y) {
                ans.add(node.second)
                break
            }
            
            if (!(visited[node.first + n] ?: false)) {
                q.add(Pair(node.first + n, node.second + 1))
                visited[node.first + n] = true
            }
            if (!(visited[node.first * 2] ?: false)) {
                q.add(Pair(node.first * 2, node.second + 1))
                visited[node.first * 2] = true
            }
            if (!(visited[node.first * 3] ?: false)) {
                q.add(Pair(node.first * 3, node.second + 1))
                visited[node.first * 3] = true
            }
        }
    }
}

통과!!!