[프로그래머스] N으로 표현

코드 힌트

1. 문제 개요:
   • 주어진 숫자 N을 최대 8번까지 사용하여 특정 숫자 number를 만들 수 있는 최소 사용 횟수를 계산합니다.
   • 덧셈, 뺄셈, 곱셈, 나눗셈과 같은 연산을 반복적으로 수행하며 최적의 해를 찾습니다.
2. 초기화:
   • N을 사용하여 만들 수 있는 모든 숫자를 HashMap에 초기화하고, 각 숫자를 만들기 위해 필요한 최소 사용 횟수를 저장합니다.
3. 재귀적 연산:
   • N을 사용하여 가능한 모든 연산을 수행하고, 결과를 HashMap에 기록합니다.
   • 이미 계산된 숫자의 경우 더 적은 횟수로 동일한 숫자를 만들 수 있는지 확인하여 업데이트합니다.
   • 8번 이상의 연산은 의미가 없으므로 재귀 깊이를 제한합니다.
4. 최종 결과:
   • HashMap에서 목표 숫자 number에 대한 최소 연산 횟수를 찾아 반환합니다.
   • 만약 목표 숫자를 만들 수 없다면 -1을 반환합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        // 숫자 N을 사용하여 만들 수 있는 모든 숫자와 그에 대한 최소 연산 횟수를 저장하는 HashMap
        HashMap<Integer, Integer> map = initMap(N);
        
        // 재귀적으로 가능한 모든 경우를 계산하여 map을 갱신
        counting(map, N, 0, 0);
        
        // 목표 숫자 number를 만들 수 있는 최소 연산 횟수를 반환
        // 찾을 수 없으면 -1 반환
        return map.getOrDefault(number, -1);
    }
    
    // 가능한 모든 연산을 수행하는 재귀 함수
    void counting(HashMap<Integer, Integer> map, int N, int current, int count) {
        // 연산 횟수가 8회 초과거나 이미 계산된 경우 종료
        if (count > 8 || (count > 0 && current == 0)) {
            return;
        }
        
        // 현재 숫자를 만들기 위한 최소 연산 횟수를 map에 저장
        map.put(current, Math.min(count, map.getOrDefault(current, count)));
        
        // 가능한 모든 N의 조합(예: N, NN, NNN)을 사용하여 연산 수행
        for (int i = N, digit = 1; i <= 111111111; i = i * 10 + N, digit++) {
            counting(map, N, current + i, count + digit); // 덧셈 연산
            counting(map, N, current - i, count + digit); // 뺄셈 연산
            counting(map, N, current * i, count + digit); // 곱셈 연산
            counting(map, N, current / i, count + digit); // 나눗셈 연산
        }
    }
    
    // 초기화 함수: 숫자 N의 반복(예: N, NN, NNN 등)을 map에 추가
    HashMap<Integer, Integer> initMap(int N) {
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // N을 반복하여 만들 수 있는 모든 숫자와 최소 연산 횟수를 저장
        for (int i = N, count = 1; i <= 111111111; i = i * 10 + N, count++) {
            map.put(i, count);
        }
        
        return map;
    }
}