[코딩테스트] Java N으로 표현

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

이 주어진 숫자 N을 여러 번 사용하여 특정 숫자 number를 만들기 위해 필요한 최소 사용 횟수를 찾는 문제를 해결합니다.
이것은 동적 계획법(Dynamic Programming, DP)을 활용하여 숫자 N을 점진적으로 조합해 나가는 방식입니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        // N을 i번 사용해서 나온 수 => dp[i] 에 저장
        List<Set<Integer>> dp = new ArrayList<>();
        
        for(int i = 0; i <= 8; i++) {
            dp.add(new HashSet<>());
        }
        
        for(int i = 1; i <= 8; i++) {
            // 5, 55, 555 ....
            int repeatN = Integer.parseInt(String.valueOf(N).repeat(i));
            dp.get(i).add(repeatN);
            
            // 사칙연산으로 찾기
            for (int j = 1; j < i; j++) {
                for (int a: dp.get(j)) {
                    for (int b : dp.get(i - j)) {
                        // +
                        dp.get(i).add(a + b);
                        // -
                        dp.get(i).add(a - b);
                        dp.get(i).add(b - a);
                        // *
                        dp.get(i).add(a * b);
                        // /
                        if (b != 0) dp.get(i).add(a / b);
                        if (a != 0) dp.get(i).add(b / a);
                    }
                }
            }
            
            if (dp.get(i).contains(number)) {
                return i;
            }
        }
        
        return -1;
    }
}

코드 설명

• 입력값 및 변수 초기화
  • dp[i]: 숫자 N을 정확히 i번 사용해서 만들 수 있는 모든 숫자의 집합입니다.
  • 문제에 나왔던대로 답은 8보다 클 수 없기에 dp는 최대 8번까지 숫자를 사용한 결과를 저장할 수 있도록 초기화합니다.
• int repeatN = Integer.parseInt(String.valueOf(N).repeat(i)); dp.get(i).add(repeatN);
  String.valueOf(N).repeat(i)를 통해 N을 i번 반복합니다.
  
  • String.valueOf(N).repeat(i): 숫자 N을 i번 반복한 문자열을 생성합니다.
  • 숫자 repeatN을 dp[i]에 추가합니다.
• 사칙연산으로 숫자 조합
  
  • j와 i - j로 숫자 N을 각각 j번, i-j번 사용해서 만든 숫자들을 조합하여 dp[i]를 채웁니다.
  • 각 숫자 쌍 (a, b)에 대해 사칙연산을 수행하고 결과를 dp[i]에 추가:
    • 덧셈: a + b
    • 뺄셈: a - b, b - a
    • 곱셈: a * b
    • 나눗셈: a / b, b / a (0으로 나누는 경우를 제외).
• if (dp.get(i).contains(number)) { return i; }
  
  • targetNumber가 있으면 현재 i를 반환합니다.