[프로그래머스] N으로 표현 (Java, DP, lv3)

 

---

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/42895#

프로그래머스

 

문제 풀이

- 동적 프로그래밍 (Dynamic Programming)

- 숫자 N과 사칙연산을 사용해서 number가 만들어지는 N의 사용횟수(1 ~ 8개) 최소값을 구하는 문제

- List 컬렉션에 Set 자료구조를 사용하여 중복을 제거하고, 연산 결과를 자리수마다 담을 수 있도록 하였다

List<Set<Integer>> data = new ArrayList<>();
for(int i = 0; i <= 8; i++) {
    data.add(new HashSet<>());
}

 

 

우선 첫 자리의 경우 N으로 초기화를 한다

사칙연산에서 덧셈과 곱셈은 교환법칙이 성립한다. 반면 뺄셈과 나눗셈은 교환 법칙이 성립 x
ex) 1 + 4 == 4 + 1 ,  1 * 4 == 4 * 1
      1 - 4  != 4 - 1,     1 / 4  != 4 / 1

 

그리고 각 자리수 마다 연속 N값을 수동으로 추가한다 (나의 경우 repeat 메소드를 뽑아서 처리했다)

- 2자리의 경우 55 추가한 이후 1자리 수에 N을 사칙연산 해준다 (set1, set1) 

- 3자리의 경우 555 추가한 이후 (set1, set2) , (set2, set1) 그룹을 사칙연산하여 조합을 구한다

- 4자리의 경우 5555 추가후 (set1, set3) , (set2, set2) , (set3, set1) 그룹을 사칙 연산 처리해서 조합을 구한다 

- 그리고 8자리 될 때까지 반복하면서, 해당 자리수 집합에 number가 있는 경우 종료한다 (없으면 -1 반환)

 

 

전체 코드

import java.util.*;
import java.util.function.BiFunction;

class Solution {
    
    public int solution(int N, int number) {
        if(N == number) return 1;
        
        List<Set<Integer>> data = new ArrayList<>();
        for(int i = 0; i <= 8; i++) {
            data.add(new HashSet<>());
        }
        
        Set<Integer> one = data.get(1); // 한자리 
        one.add(N);
     
        for(int i = 2; i <= 8; i++) {
            Set<Integer> cur = data.get(i);
            cur.add(repeat(N, i));
            
            for(int j = 1; j < i; j++) {
                Set<Integer> set1 = data.get(j);
                Set<Integer> set2 = data.get(i - j);
                
                for(int v1 : set1) {
                    for(int v2 : set2) {
                        cur.add(v1 + v2);
                        cur.add(v1 - v2);
                        cur.add(v1 * v2);
                        if(v2 != 0) {
                            cur.add(v1 / v2);
                        }
                    }
                }
            }
            
            if(cur.contains(number)) {
                return i;
            }
        }
        
        return -1;
    }
    
    private int repeat(int base, int n) {
        int result = 0;
        for(int i = 0; i < n; i++) {
            result *= 10;
            result += base;
        }
        return result;
    }
    

    
}