[프로그래머스 Level.2] 숫자 변환하기 (연습문제) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 연습문제 > 숫자 변환하기

 

 

 

문제 설명

 

 

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

 

---

입출력 예 설명

 

 

입출력 예 #1

x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

 

 

 

입출력 예 #2

x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

 

 

 

입출력 예 #3

x를 y로 변환할 수 없기 때문에 -1을 return합니다.

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        
        Set<Integer> curSet= new HashSet<>();
        Set<Integer> nextSet;
        curSet.add(x);
        
        while(!curSet.isEmpty()) {
            if(curSet.contains(y)) return answer;
            
            nextSet = new HashSet<>();
            for(int c : curSet) {
                if(c + n <= y) nextSet.add(c + n);
                if(c * 2 <= y) nextSet.add(c * 2);
                if(c * 3 <= y) nextSet.add(c * 3);
            }
            
            curSet = nextSet;
            answer++;
        }
        
        return -1;
    }
}

 

풀이

1. 우선 Integer를 선언타입으로 하는 Set을 curSet을 생성하고 x를 담는다.
2. curSet이 빌 때까지 while문을 돌리며 curSet이 y의 값을 갖게되면 answer를 반환한다.
3. nextSet을 생성하고 curSet을 for each문을 돌리면서 curSet에 있는 값을 꺼내 문제에 주어진대로 해당 값 + n, 해당 값 * 2, 해당 값 * 3을 해서 y 이하라면 nextSet에 담는다. (y보다 크면 y가 될 수 없으므로 담지 않는다)
4. 그리고 nextSet을 curSet으로 하고 한 번 연산을 한 것이므로 answer를 1 증가시킨다.
5. curSet이 빌 때까지 while문을 돌렸음에도 y 값을 구하지 못했다면 -1을 반환한다.