프로그래머스 Level2 숫자 변환하기

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

문제

• 자연수 x를 y로 다음과 같은 방법으로 변환하려고 한다.
  • x에 n을 더한다.
  • x에 2를 곱한다.
  • x에 3을 곱한다.
• x를 y로 변환하기 위한 최소 연산 횟수를 구하시오. 변환할 수 없다면 -1을 반환하시오.

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

코드

import java.util.*;
public class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        HashSet<Integer> cur = new HashSet<>();
        cur.add(x);
        while(!cur.isEmpty()) {
            if(cur.contains(y)) {
                return answer;
            }

            HashSet<Integer> next = new HashSet<>(); 
            for(int num : cur) {
                if(num + n <= y) {
                    next.add(num+n);
                }

                if(num*2 <= y) {
                    next.add(num*2);
                }

                if(num*3 <= y) {
                    next.add(num*3);
                }
            }
            cur = next;
            answer++;
        }
        return -1;
    }
}

풀이

• y의 최대값이 백만이고, 3가지 연산을 계속해서 해야하기 때문에 3배씩 늘어날 것을 생각하면 재귀로는 풀 수 없는 문제다.
• 각각의 값이 중복될 수 있기 때문에 Set을 통해 해결한다. 또한 현재 계산했던 x의 값들을 set에 남기면 또 그것을 다시 계산해야할 수 있기 때문에 새롭게 계산을 통해 나온 값들의 Set으로 바꾸어 주어야 한다.