[Programmers / Level2] 154538. 숫자 변환하기(Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154538
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/154538. 숫자 변환하기

입출력 조건

입출력 예시

문제 이해

• 주어진 연산에 맞게 변환할 수 있는 최소 연산 횟수를 반환하는 문제

알고리즘

풀이 시간 : 1시간 10분

• 동적 프로그래밍 이용 : dp[i+연산결과] == 0 || 기존 값 > dp[i] + 1 -> 갱신
  • x에 n을 더하는 경우
    • i+n이 y 이하라면 -> dp[i+n] 반환
  • x에 2를 곱하는 경우
    • i2가 y 이하라면 -> dp[i2] 반환
  • x에 3을 곱하는 경우
    • i3이 y 이하라면 -> dp[i3] 반환
  • 변환이 안되는 경우 -> -1 반환

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        int[] dp = new int[y+1];
        
        for(int i = x; i <= y; i++) {
            // 변환할 수 없는 값이면 -1로 설정
            if(i != x && dp[i] == 0) {
                dp[i] = -1;
                continue;
            }
            
            // x에 n을 더한 값
            if(i + n <= y) {
                if(dp[i + n] == 0) {
                    dp[i + n] = dp[i] + 1;
                } else {
                    if(dp[i] + 1 < dp[i + n]) {
                        dp[i + n] = dp[i] + 1;
                    }
                }
            }
            
            // x에 2를 곱한 값
            if(i * 2 <= y) {
                if(dp[i * 2] == 0) {
                    dp[i * 2] = dp[i] + 1;
                } else {
                    if(dp[i] + 1 < dp[i * 2]) {
                        dp[i * 2] = dp[i] + 1;
                    }
                }
            }
            
            // x에 3을 곱한 값
            if(i * 3 <= y) {
                if(dp[i * 3] == 0) {
                    dp[i * 3] = dp[i] + 1;
                } else {
                    if(dp[i] + 1 < dp[i * 3]) {
                        dp[i * 3] = dp[i] + 1;
                    }
                }
            }
        }
        return dp[y];
    }
}

오답체크

//before

//after

최종 풀이

풀이 시간 : 분(첫 풀이 시간 포함)

결과

🚨 참고할 풀이

• if문 내부를 삼항 연산자를 사용해 코드 리팩토링 가능
• 출처 : [프로그래머스] 숫자 변환하기 ⭐

import java.math.*;
class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        int[] dp = new int[y+1];
        
        for(int i=x; i<=y; i++) {
            // 변환할수 없는 값이면 -1;
            if(i!=x && dp[i] == 0) {
                dp[i] = -1;
                continue;
            }
            
            // x에 n을 더한 값
            if(i+n <= y) {
                dp[i+n] = (dp[i+n] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i+n]);
            }
            
            // x에 2를 곱한 값
            if(i*2 <= y) {
                dp[i*2] = (dp[i*2] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i*2]);
            }
            
            // x에 3을 곱한 값
            if(i*3 <= y) {
                dp[i*3] = (dp[i*3] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i*3]);
            }
        }

        return dp[y];
    }
}