프로그래머스 코딩테스트 연습 | 숫자 변환하기

코딩테스트 연습 문제 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
  

접근 방법

• 알고리즘 종류 : BFS

• dp로도 풀 수 있는데 시작할 때 bfs로 접근을 해서 bfs로 풀었다. x가 할 수 있는 연산은 3가지 이므로 해당 연산으로 이동함. 만약 들린적이 있다면 그 값이 최소이므로 들리지 않고, 들린 적 없다면 que에 넣어줌. y가 될때까지 연산하기

import java.util.*;
class Solution {
    public int solution(int x, int y, int n) {
        boolean[] visited = new boolean[y+1];
        int answer = -1;
        
        Queue<Loc> que = new LinkedList();
        que.add(new Loc(x,0));
        Loop1: while(!que.isEmpty()){
            Loc now = que.poll();
            
            int[] nrArr = {now.loc+n, now.loc*2, now.loc*3};
            int nIter = now.iter+1;
            
            for(int i=0; i<3; i++){
                int nr = nrArr[i];
                if(nr==y){
                    answer = nIter;
                    break Loop1;
                }else if(nr<visited.length && !visited[nr]){
                    visited[nr] =true;
                    que.add(new Loc(nr, nIter));
                }
            }
        }
        
        if(x==y){
            return 0;
        }
        return answer;
    }
    static class Loc{
        int loc;
        int iter;
        public Loc(int loc, int iter){
            this.loc = loc;
            this.iter = iter;
        }
    }
}

# Thinking

클래스 정의를 하는 방법을 잘 기억해둘 것.