프로그래머스 154538 숫자 변환하기 자바 풀이

난이도 : Lv. 2

풀이일 : 2410255

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

프로그래머스

---

문제

---

아이디어

• BFS 탐색으로 x가 y될 때까지 필요한 변환 횟수를 기록하자
• y 크기의 배열에 기록하고, x 변환 후 y가 넘어가는 경우는 기록하지 않는다

---

풀이

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

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        int[] counts = new int[y+1];
        int[] di = {n, 2, 3};
        
        counts[x] = 1;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        
        while (!queue.isEmpty()) {
            int i = queue.poll();
            for (int k = 0; k < 3; k++) {
                int ni = k == 0 ? i + di[k] : i * di[k];
                if (ni <= y) {
                    if (counts[ni] < 1 || counts[ni] > counts[i] + 1) {
                        counts[ni] = counts[i] + 1;
                        queue.add(ni);
                    }
                }   
            }
        }
        answer = counts[y] > 0 ? counts[y]-1 : -1;
        
        return answer;
    }
}

• queue를 생성하여, 이동할 자리를 넣고, di를 이용해 다음 이동할 자리 탐색
• 다음 이동할 자리가 y보다 작다면, 조건검사
  • counts[ni] 가 0이어서 방문한 적이 없거나, 기록된 변환 횟수보다 현재 방법의 변환횟수가 적다면 counts[i] 갱신하고 queue에 추가
• 반복문이 끝난 후, counts[y]에 기록된 방문횟수가 있다면 answer에 재할당, 없다면 방문할 수 없으므로 -1 재할당

---

느낀점

• 디피로도 풀어봐야지