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

• N으로 표현

풀이과정

각 단계별로(숫자 N을 i번 사용) 표현할 수 있는 수는 크게 두 종류로 구분할 수 있다.

1. N을 i번 이어 붙인 경우
2. 이전 단계의 결과를 서로 사칙연산한 결과

예를 들어, 4번 째 단계라면 다음과 같은 경우의 수를 갖는다.

• N을 4번 이어붙인 경우
• N을 3개 사용한 경우(바로 이전 단계)와 N을 1개(= 4 - 3)만 사용한 경우의 사칙연산
• N을 2개 사용한 경우(전전 단계)와 N을 2개(= 4 - 2)만 사용한 경우의 사칙연산
• N을 1개 사용한 경우(전전전 단계)와 N을 3개(= 4 - 1)만 사용한 경우의 사칙연산

이를 통해 특정 숫자 N만을 활용하여 어떤 임의의 정수 k를 만들 수 있는 방법은 다음과 같이 전개하여 찾을 수 있다.

1. i개의 N을 사용하여 표헌할 수 있는 모든 수를 찾는다.
   • N 을 i개 이어붙인 것
   • N을 i - 1개 사용한 경우와 N을 1회 사용한 경우의 사칙연산
   • N을 i - 2개 사용한 경우와 N을 2회 사용한 경우의 사칙연산
   • …
   • N을 1개 사용한 경우와 N을 i - 1회 사용한 경우의 사칙연산
2. 1의 결과로 나온 수들 중 주어진 target number가 있는지 확인한다. 있다면 i를 반환하고, 없다면 i를 1 증가시키고 다시 1의 과정을 수행한다.
3. 8개의 N을 사용해도 target number를 표현할 수 없다면, 문제에 주어진 조건에 따라 -1을 return 한다.

Code

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

class Solution {
    public int solution(int N, int number) {
        List<Set<Integer>> result = new ArrayList<>();

        for (int i = 0 ; i < 8; i++) {
            result.add(new HashSet<>());
        }
        result.get(0).add(N); // N을 1개만 사용할 경우, N 자신만 표현 가능

        for (int i = 0; i < 8; i++) {
            Set<Integer> currentResult = result.get(i);
            // 1. N을 (i + 1)번 이어붙인 경우
            currentResult.add(Integer.parseInt(String.valueOf(N).repeat(i + 1)));

            // 2. 이전 단계의 결과를 서로 사칙연산한 결과
            // [N을 1개 사용한 경우] union [(i + 1) - 1개 사용한 경우]
            // [N을 2개 사용한 경우] union [(i + 1) - 2개 사용한 경우]
            // ...
            for (int j = 0; j < i; j++) {
                for (int case1 : result.get(j)) {
                    for (int case2 : result.get(i - 1 - j)) {
                        currentResult.add(case1 + case2);
                        currentResult.add(case1 - case2);
                        currentResult.add(case1 * case2);
                        if (case2 != 0) {
                            currentResult.add(case1 / case2);
                        }
                    }
                }
            }

            if (currentResult.contains(number)) {
                return i + 1;
            }
        }

        return -1;
    }
}

결과