[프로그래머스] N으로 표현 - JAVA [자바]

링크

문제는 상당히 직관적이라 굳이 문제 설명은 필요가 없을 것 같다.

한가지 포인트는 N, NN, NNN 숫자를 이용할 때 Integer.toString(N).repeat(i))를 이용했다.

이거는 JDK 11이상 지원으로, JDK 8 제한 코테에서 사용하려면 반복문 통해서 해결해야 된다. 추가로, repeat() 메서드는 byte 배열을 이용하여, native인 System.arrayCopy()를 이용하여 최적화 되어있다.

풀이

import java.util.*;  
  
class Solution {  
  
    public int solution(int N, int number) {  
        // N을 x번 사용해서 만들 수 있는 수들을 저장하는 배열  
        Set<Integer>[] dp = new Set[9];  
        for (int i = 1; i <= 8; i++) {  
            dp[i] = new TreeSet<>();  
        }  
        // N을 x번 사용해서 만들 수 있는 기본 폼인 NNNN 꼴 저장  
        for (int i = 1; i <= 8; i++) {  
            dp[i].add(Integer.parseInt(Integer.toString(N).repeat(i)));  
        }  
        // 기본 폼들을 이용하여, N을 x번 사용해서 만들 수 있는 모든 경우의 수를 저장  
        for (int i = 1; i <= 8; i++) {  
            for (int j = 1; j < i; j++) {  
                for (int k : dp[j]) {  
                    for (int l : dp[i - j]) {  
                        dp[i].add(k + l);  
                        dp[i].add(k - l);  
                        dp[i].add(k * l);  
                        if (l != 0) {  
                            dp[i].add(k / l);  
                        }  
                    }  
                }  
            }  
        }  
        int answer = -1;  
        for (int i = 1; i <= 8; i++) {  
            if (dp[i].contains(number)) {  
                answer = i;  
                break;  
            }  
        }  
        return answer;  
    }  
}

1개 부터 시작해서, 8개까지 이용하는 경우의 수를 점화식 or 재귀적으로 풀어보려했는데 솔직히 모르겠어서 그냥 x개를 사용했을 때, 만들 수 있는 숫자들을 저장하는 방식으로 갔다.

기본 폼을 떠올린 거가 제일 큰 수확같은데, N, NN, NNN 꼴인 레고 블럭으로 특정 수들을 조립한다는 접근이었다.

솔직히 가능한 경우의 수 다 때려박는 접근이라 될 지는 몰랐는데 됐다. 패스 후에 다른 사람들의 코드를 봤는데, 솔직히 다 직관적이지도 않고, 애매한 거 같다.