[level 2] 숫자 변환하기 - 154538

[level 2] 숫자 변환하기 - 154538

문제 링크

성능 요약

메모리: 161 MB, 시간: 255.38 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 10월 07일 20:26:52

문제 설명

자연수 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) {
        Set<Integer> visited = new HashSet<>();
        Queue<int[]> q = new LinkedList<>();
        
        q.add(new int[]{x,0});
        visited.add(x);
        while(!q.isEmpty()){
            int[] curX = q.poll();
            
            if(curX[0] == y){
                return curX[1];
            }
            
            if(curX[0]<y){
                if(!visited.contains(curX[0] * 2) && curX[0]*2<=y){
                    q.offer(new int[]{curX[0] * 2, curX[1] + 1});
                    visited.add(curX[0] * 2);
                }
                if (!visited.contains(curX[0] * 3) && curX[0]*3<=y){
                    q.offer(new int[]{curX[0] * 3, curX[1] + 1});
                    visited.add(curX[0] * 3);
                } 
                if (!visited.contains(curX[0] + n) && curX[0]+n<=y){
                    q.offer(new int[]{curX[0] + n, curX[1] + 1});
                    visited.add(curX[0] + n);
                }
            }
            
        }
        return -1;
    }
}