<프로그래머스> 숫자 변환하기(Lv.2)
[깃허브]
[프로그래머스]
https://school.programmers.co.kr/learn/courses/30/lessons/154538
문제 지문이 짧으면 짧을수록 나의 마음은 더욱 떨려온다...
그래도 이 문제는 금방 풀 수 있었다.
그건 바로 이러한 유형의 문제들을 풀었던 경험이 남아있었기 때문이다.
문제를 보자마자 생각이 든 것은 DP였다.
최소 연산 횟수라는 말이 가장 큰 포인트였다.
그렇게 보게 되니까 DP 문제 중에 유명한(?) 문제 중에 하나인 '1로 만들기' 문제가 생각나서 그 방식대로 코드를 짰다.
그런데 틀렸다...?!
완전히 다 틀리는 건 아니고 20퍼정도를 실패했다.
물론 그 중에 하나는 x와 y가 같을 때를 고려하지 않았던 거라 금방 해결했지만 그 외의 케이스는 잡지 못했다.
풀고 나서 이리 저리 만져보면서 해도 해결하지 못했다...
그래서 다음으로 든 생각은 'BFS도 되겠는데?'였다.
BFS 문제 유형 중에서 '숨바꼭질'이라는 게 있는데 그것도 이러한 유형이었다는 게 생각났다.
그렇게 코드를 작성하고 제출했더니 맞았다..!!
상향식으로 하든지, 하향식으로 하든지 둘다 정답이 나오더라(당연한 거기는 하지...)
상당히 오랜만에 BFS라서 약간 희미했지만 금방 회복했다.
해당 방법으로 작성한 코드는 다음과 같다.
class Solution {
fun solution(x: Int, y: Int, n: Int): Int {
// x와 y가 같다면 0
if (x == y) return 0
var dp = IntArray(y + 1) { 0 }
var q = ArrayDeque<Int>()
q.add(x)
while (!q.isEmpty()) {
val cur = q.removeFirst()
if (cur + n <= y && dp[cur + n] == 0) {
dp[cur + n] = dp[cur] + 1
q.add(cur + n)
}
if (cur * 2 <= y && dp[cur * 2] == 0) {
dp[cur * 2] = dp[cur] + 1
q.add(cur * 2)
}
if (cur * 3 == 0 && dp[cur * 3] == 0) {
dp[cur * 3] = dp[cur] + 1
q.add(cur * 3)
}
}
return if (dp[y] == 0) -1 else dp[y]
}
}
dp로 하는 방식을 해결하게 되면 이곳에 추가해놓겠다..!!
해결했다..!
중요했던 것은 BFS와 DP가 다르다는 걸 인지해야하는 것이었다.
BFS를 상향식으로 하든지, 하향식으로 하든지 이 방식에서는 조건에 맞는 값들만 쏙쏙 빼서 진행하게 되지만 DP는 모든 값을 순회하는 형식을 짜기 때문에 초기값이 매우 중요했다.
원하지 않는 값을 가져오게 되는 경우에 적용시키지 않기 위해..!!
그래서 배열의 초기값을 0에서 계산 중에 나올 수 없는 큰 값인 1000000으로 설정하고 시작 위치인 x의 dp[x]는 0으로 변경했다.(감사합니다... 이 풀이로 해결해주신 분...)
그리고 사용할 수 있는 연산 중에서 첫번째를 적용할 때 이전에는 그냥 (값 + 1)을 집어넣는 식으로 했었는데 그렇게 하니까 틀리는 케이스가 존재하더라
그래서 minOf를 사용하여 집어넣으니까 해결되었다.
사실 이 케이스는 왜 그런지 잘 모르겠다.
무조건 (i - n)이 x보다 클 때 적용되니까 문제가 없는 거 같은데...
여러 시도 끝에 통과했지만 완벽히 이해하지는 못했기에 아쉽다.
반례 찾는 것만 되면 이해에 도움이 될텐데... 이건 어떻게 키울 수 있을까?
(해당 코드도 깃허브에 업데이트 되었다.)