[Lv. 2] 숫자 변환하기

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

난이도 : Level.2

언어 : Kotlin

 

문제 설명 :

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

입출력 예 :

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

다른 사람의 풀이 : 

import java.util.LinkedList
import java.util.Queue

lateinit var answer: ArrayList<Int>
lateinit var queue: Queue<Pair<Int, Int>>
lateinit var visited: HashMap<Int, Boolean>

class Solution {
    fun solution(x: Int, y: Int, n: Int): Int {
        answer = arrayListOf()
        queue = LinkedList()
        visited = hashMapOf()

        bfs(x, y, n, 0)

        return if (answer.isEmpty()) -1 else answer.first()
    }

    fun bfs(x: Int, y: Int, n: Int, depth: Int) {
        queue.add(Pair(x, depth))

        while (queue.isNotEmpty()) {
            val node = queue.poll()

            if (node.first > y) continue
            if (node.first == y) {
                answer.add(node.second)
                break
            }

            if (visited[node.first + n] != true) {
                queue.add(Pair(node.first + n, node.second + 1))
                visited[node.first + n] = true
            }
            if (visited[node.first * 2] != true) {
                queue.add(Pair(node.first * 2, node.second + 1))
                visited[node.first * 2] = true
            }
            if (visited[node.first * 3] != true) {
                queue.add(Pair(node.first * 3, node.second + 1))
                visited[node.first * 3] = true
            }
        }
    }
}

 

DFS/BFS 이 쪽에 내가 많이 약하다는 것을 느꼈다.

알고리즘쪽으로 전반적으로 약한게 아닐까 싶어 그쪽 공부를 좀 더 보충하는게 좋겠다는 생각이 든다.

 

다음은 DFS, BFS에 대한 전반적인 설명 및 자세한 풀이가 첨부된 링크다.

 

https://dev-musa.tistory.com/entry/DFS-BFS-Kotlin

DFS & BFS ( Kotlin )

https://velog.io/@wonseok/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv.2-%EC%88%AB%EC%9E%90-%EB%B3%80%ED%99%98%ED%95%98%EA%B8%B0

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