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

풀이방식

상단부

1. Set 배열 생성
2. Set 배열 순회
3. 배열 각 인덱스마다 HashSet 객체 생성 후 저장
4. HashSet마다 NN..(for문 반복 횟수)..N 저장

중단부

1. Set 배열 순회
2. a의 Set 인덱스 == A == j : 1부터 i-1까지 순회
3. b의 Set 인덱스 == B == (i-j) == (i-A) == A와 더했을 때 i가 되는 수
4. a와 b의 사칙연산 조합을 Set[i]에 저장
5. 중복 제거 -> A(j)가 B(i-j)보다 커지면 스킵

하단부

1. Set 배열 순회
2. number가 있으면 해당 인덱스 번호(조합 횟수)가 정답

포인트

해당 알고리즘 내 Set의 의미

Set[i] == N을 i번 조합해 만든 숫자들의 집합

고민

중복의 발견

알고리즘을 이해하는 과정 중, 중단부에서 두 집합을 조합하여 새로운 집합을 만들고 있다는 것을 알았다

그런데 N을 i번 조합하는 것이 (j번 조합하는 것 + (i-j)번 조합하는 것)이라면 그 반대의 경우도 똑같은 것 아닌가?

case 1. A = j, B = i-j 일 때, A와 B를 조합해서 만든 집합
case 2. A = i-j, B = j 일 때, A와 B를 조합해서 만든 집합

case 1과 case 2의 결과 집합은 같을 것이다

그래서 중복을 없애주기 위해 A가 B보다 커지는 순간, 반복문을 스킵해버리기로 했다

if(j > i-j) break;

구현

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

public class NUM42895 {
    public static void main(String[] args) {
        int N = 2;
        int number = 11;
        System.out.println(solution(N, number));
    }
    public static int solution(int N, int number) {
        int answer = 0;
        answer = -1;

        Set<Integer>[] combination = new Set[9];
        int NN = N;
        for(int i = 1; i < 9; i++) {
            combination[i] = new HashSet<>();
            combination[i].add(NN);
            NN = NN * 10 + N;
        }

        for(int i = 1; i < 9; i++) {
            for(int j = 1; j < i; j++) {
                if(j > i-j) break;
                for(Integer a : combination[j]) {
                    for(Integer b : combination[i - j]) {
                        // System.out.println("a = "+a+" // b = "+ b+ " // j = "+j+ " // i-j = "+ (i-j)+" // i = "+i);
                        combination[i].add(a + b);
                        combination[i].add(a - b);
                        combination[i].add(b - a);
                        combination[i].add(a * b);
                        if(b != 0) { combination[i].add(a / b); }
                        if(a != 0) { combination[i].add(b / a); }
                    }
                }
            }
        }

        for(int i = 1; i < 9; i++) {
            if(combination[i].contains(number)) { answer = i; break; }
        }

        return answer;
    }
}

---

*다른 분들의 코드를 참고하여 작성했습니다