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

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

프로그래머스

---

문제 분석

•  
• N과 number가 주어진다. 
• N과 사칙연산(+, -, *, /)만 이용해서 number을 표현할 때 n의 사용개수를 반환해라
  • 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
  • 12 = 5 + 5 + (5 / 5) + (5 / 5)
    12 = 55 / 5 + 5 / 5
    12 = (55 + 5) / 5
• N은 1 이상 9 이하입니다. 
• number는 1 이상 32,000 이하입니다. 
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 
• 최솟값이 8보다 크면 -1을 return 합니다.

+ 추가적으로 22는 사칙연산 없이 2를 두번 써서 만들 수 있으므로, 리턴 값은 2이다.

---

해결 키 포인트

 

•  dp 이용 
• dp를 각 숫자 index로만 생각하지 말 것 !
• dp를 "N을 사용한 횟수" 로 사용
  • dp[1] : N을 1번 사용해서 만들 수 있는 숫자 Set
    ...
    dp[8] : N을 1번 사용해서 만들 수 있는 숫자 Set
    [ 최솟값이 8보다 크면 -1을 return ! ]
• dp를 Set으로 사용 : Set을 이용한 이유 - 중복 제거를 위해 
  • <Set<Integer>> dp [] 
  • <List<Set<Integer>>> dp 

ArrayList : 순서 보장 O , 중복 제거 X
Set : 순서 보장 X , 중복 제거 O

 

• dp[n]에 포함되는 숫자 : dp[i]에 포함되는 숫자 + dp[n-i]에 포함되는 숫자
  
  • 해당 문제에서는 괄호연산이 가능하기 때문에 둘의 연산을 반대로 하는 경우도 신경써줘야 한다.
  • ex) 5 + 5 * 5와 (5 + 5) * 5가 다르기 때문에
• 연속된 숫자도 삽입 (String.repeat 사용)
  • String n = Integer.toString(N);
    dp[i].add(Integer.parseInt(n.repeat(i)));

 

---

코드

 

import java.util.HashSet;
import java.util.Set;

class Solution {
    public static void main(String[] args) {
        new Solution().solution(5, 11);
    }

    public int solution(int N, int number) {

        Set<Integer> [] dp = new Set[9];

        for (int i = 0; i < 9; i++) {
            dp[i] = new HashSet<>();
        }

        dp[1].add(N);
        if(N == number)
            return 1;
        
        for (int i = 2; i < 9; i++) {
            for (int j = 1; j <= i/2; j++) {
                unionSet(dp[i], dp[j], dp[i-j]);
                unionSet(dp[i], dp[i-j], dp[j]);
            }
            String n = Integer.toString(N);
            dp[i].add(Integer.parseInt(n.repeat(i))); //연속된 숫자 넣기
            for(int num : dp[i]) {
                if(num == number)
                    return i;
            }
        }

        return -1;
    }

    public void unionSet(Set<Integer> union, Set<Integer> a, Set<Integer> b) {
        for (int n1 : a) {
            for(int n2 : b) {
                union.add(n1 + n2);
                union.add(n1 - n2);
                union.add(n1 * n2);
                if(n2 != 0)
                    union.add(n1/n2);
            }
        }
    }
}