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

코딩테스트 연습 - 숫자 변환하기

문제 설명

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

풀이

To-Do 리스트

1. 처음 값을 넣고 구하려는 값보다 작거나 같은 수인 경우의 수의 값을 넣음.
2. 작거나 같은 수가 하나도 없는 경우 -1 리턴
3. 같은 수가 있다면 반복한 횟수 출력.

결과

import java.util.*;
class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        // 경우의 수 : 3
        // x+n | x*2 | x*3
        // 최소 연산 횟수 구하기 (단, 만들수 없다면 -1)
        Set<Integer> list = new HashSet<>();
        Set<Integer> tmp = null;
        list.add(x);
        
        while(!list.isEmpty()){
            tmp = new HashSet<>();
            if(list.contains(y)) break;
 
            for(int i : list){
                if(i+n <= y) tmp.add(i+n);
                if(i*2 <= y) tmp.add(i*2);
                if(i*3 <= y) tmp.add(i*3);
            }
            list = tmp;
            answer++;
        }
        if(list.isEmpty()) answer = -1;
        
        return answer;
    }
}