[프로그래머스] 숫자 변환하기 -JAVA

[프로그래머스] 코딩테스트 연습 > 연습문제 > 숫자 변환하기

문제 설명

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

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

---

해설

시간초과때문에 꽤나 힘들었던 문제였다.
충분히 Collection을 잘 활용한다고 생각하였으나 아니었다.
더더더 잘 활용해보자.

코드

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int cnt = 0;
		HashSet<Integer> set = new HashSet<>();
		HashSet<Integer> next = null;

		set.add(x);
		while (!set.isEmpty()) {
			if (set.contains(y))
				return cnt;

			next = new HashSet<>();
			for (int val : set) {
				if (val + n <= y)
					next.add(val + n);
				if (val * 2 <= y)
					next.add(val * 2);
				if (val * 3 <= y)
					next.add(val * 3);
			}
			
			set = next;
			cnt++;
		}

		return -1;
	}
}