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

프로그래머스 N으로 표현

유형

• 동적계획법(Dynamic Programming)

코드

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.IntStream;

class Solution {
    public int solution(int N, int number) {
        List<Set<Integer>> numList = new ArrayList<>();
        IntStream.range(0, 9).forEach(i -> numList.add(new HashSet<>()));

        int answer = -1;

        if(N == number) {
            answer = 1;
            return answer;
        } else {
            numList.get(1).add(N);
        }

        for(int i = 2; i < 9; i++) {
            Set<Integer> candidateList = new HashSet<>();
            for(int j = 1; j < i/2 + 1; j++) {
                int I = i;
                int J = j;
                numList.get(j).forEach(numI -> {
                    numList.get(I - J).forEach(numJ -> {
                        candidateList.add(numI + numJ);
                        candidateList.add(numI - numJ);
                        candidateList.add(numJ - numI);
                        candidateList.add(numI * numJ);
                        if(numJ != 0) candidateList.add(numI / numJ);
                        if(numI != 0) candidateList.add(numJ / numI);
                    });
                });
            }
            candidateList.add(makeNum(N, i));

            long count = candidateList.stream()
                    .filter(candidate -> candidate == number)
                    .count();

            if(count != 0) {
                answer = i;
                break;
            }

            numList.get(i).addAll(candidateList);
        }
        System.out.println("answer = " + answer);
        return answer;
    }

    private int makeNum(int n, int len) {
        int num = 0;
        for(int i = 0; i < len; i++) {
            num += n * Math.pow(10, i);
        }
        return num;
    }
}