[프로그래머스 Level.3] N으로 표현 (동적계획법(Dynamic Programming)) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 동적계획법(Dynamic Programming) > N으로 표현

 

 

 

문제 설명

 

 

 

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

 

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

 

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.

이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

 

 

 

 

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

 

 

 

입출력 예

N	number	return
5	12	4
2	11	3

 

 

입출력 예 설명

 

 

예제 #1

문제에 나온 예와 같습니다.

 

 

 

 

예제 #2

11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        int answer = -1;
        
        ArrayList<HashSet<Integer>> list = new ArrayList<>();
        
        for(int i=0; i<10; i++) {
            list.add(new HashSet<>());
        }
        
        for(int i=1; i<10; i++) {
            HashSet<Integer> set = list.get(i);
            set.add(Integer.parseInt(String.valueOf(N).repeat(i)));
            
            for(int j=1; j<i; j++) {
                HashSet<Integer> set1 = list.get(j);
                HashSet<Integer> set2 = list.get(i-j);
                
                for(int s1 : set1) {
                    for(int s2 : set2) {
                        set.add(s1 + s2);
                        set.add(s1 * s2);
                        set.add(s1 - s2);
                        
                        if(s2 != 0) 
                            set.add(s1 / s2);
                    }
                }
            }
            
            if(set.contains(number)) {
                answer = i;
                break;
            }
            
        }
        
        return answer;
    }
    
}

 

풀이

1. N을 8개를 사용해도 number를 구하지 못하면 -1을 반환하므로 answer를 -1로 초기화 한다.
2. 각 인덱스에 Set을 가지는 ArrayList를 생성한다.
3. ArrayList의 각 인덱스 i에 있는 Set에는 N을 i 개를 사용하여 만들 수 있는 수들이 담겨진다.
4. 1부터 9까지 for문을 돌면서 우선 N을 i개만큼 연속으로된 수를 담는다.
   (예를들어 N이 5이고 i가 1이면 5, i가 2이면 55, i가 3이면 555, i가 8이면 55555555)
5. 그리고 나머지 만들 수 있는 수들을 담기 위해 j를 1부터 i - 1까지 for문을 돌면서 ArrayList에서 j인덱스의 Set을 가져와 set1에 저장하고 ArrayList에서 (i - j)인덱스의 Set을 가져와 set2에 저장한 후에 set1과 set2를 이중 for each문을 이용해 각각 모든 수끼리 + , *, - 연산을 진행하고 나누는 수가 0이 아니라면 / 연산도 진행하여 ArrayList의 해당 i 인덱스의 Set에 담는다. (숫자의 순서가 바뀌면 연산의 결과가 달라지는 연산이 있으므로 모두 진행한다. 각 Set에 담긴 숫자들은 해당 숫자를 구하기 위해 괄호를 치고 먼저 연산을 진행한 것과 같다)
6. 예를 들어 N이 5라면 다음과 같이 j와 i - j에 해당하는 Set을 가져와 모두 연산하고 담는다.  
   i가 1일 때는 5를 추가한 후 for문은 넘어가고
   i가 2일 때는 55 추가 , (j = 1, i - j = 1)
   i가 3일 때는 555 추가 , (j = 1, i - j = 2) , (i = 2 , i - j = 1)
   i가 4일 때는 5555 추가 , (j = 1, i - j = 3) , (i = 2 , i - j = 2), (i = 3 , i - j = 1)
   i가 5일 때는 55555 추가 , (j = 1, i - j = 4) , (i = 2 , i - j = 3),  (i = 3 , i - j = 2), (i = 4 , i - j = 1)
   .....
   i가 8일 때는 55555555 추가 , (j = 1, i - j = 7) , (i = 2 , i - j = 6),  (i = 3 , i - j = 5), (i = 4 , i - j = 4), (j = 5, i - j = 3) , (i = 6 , i - j = 2),  (i = 7 , i - j = 1)
7. 이렇게 각 인덱스에 해당하는 개수만큼 N을 이용하여 모든 값을 구했다면 해당 인덱스의 Set에 number가 포함하는지 확인하고 포함한다면 해당 인덱스가 number를 만들 수 있는 N의 개수의 최솟값이므로 answer에 저장하고 반환하면 된다.

 

참고 : https://small-stap.tistory.com/65