LV2 - 숫자 변환하기 (Java)

 

---

 

문제

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

프로그래머스

 

 

풀이

dp? bfs 스러운 문제이다.

 

x로부터 조건에 맞게 값을 더해주거나 곱해주면서 뻗어가면서,

해당 값이 몇번만에 만드는지 파악해야한다.

 

값을 몇번만에 만드는지 저장할 array가 있어야하고,

bfs를 수행할 덱을 선언한다.

 

처음 x값을 0으로 설정한다음 이 값으로 부터 bfs를 수행한다.

방문 여부 및 한계값을 체크한다음, 조건에 만족한다면 기존 값을 만드는 횟수 + 1 을 

배열에 저장해주면 된다.

 

dfs 로도 시간은 되나, 스택오버플로우가 걸리므로 bfs로 풀이하면 된다.

 

코드

import java.util.*;

class Solution {
    public int answer = Integer.MAX_VALUE;
    public int[] nums = new int[1000001]; // visiting array
    public Deque<Integer> deq = new ArrayDeque<>();
    public int lim = 1000000; // limit
    
    public int solution(int x, int y, int n) {
        Arrays.fill(nums, Integer.MAX_VALUE);
        deq.addLast(x);
        nums[x] = 0; // 방문처리

        // deque check
        while(!deq.isEmpty()){
            int target = deq.pollFirst();
            int count = nums[target];
            
            visitCheck(target + n, count+1);
            visitCheck(target * 2, count+1);
            visitCheck(target * 3, count+1);
        }

        return nums[y] == Integer.MAX_VALUE ? -1 : nums[y];
    }

    public void visitCheck(int value, int cnt) {
        if(value > lim) return;
        
        if(nums[value] == Integer.MAX_VALUE){
            nums[value] = cnt;
            deq.addLast(value);
        }
    }
}

 

후기

 

처음에 dfs로 했을때 계속 런타임에러가 났는데 스택 문제였다.

bfs가 일반적으로는 문제 풀이에 더 용이한 거 같다.