[프로그래머스] 42895. N으로 표현

문제 링크

[프로그래머스] 42895. N으로 표현

풀이 과정

N을 최대로 사용할 수 있는 횟수는 8번 입니다. N을 한 번 ~ 여덟 번 까지 사용해서 만들 수 있는 수를 각각 구해놓고, 찾고자 하는 number 가 N을 몇 번 사용했을 때 만들어 지는지 확인하면 됩니다.

아래, 문제의 예시를 살펴보겠습니다.

N : 5, number : 12

주어진 N은 5이고, 만들고자 하는 숫자는 12입니다.

1. 5를 한 번 사용했을 때 만들 수 있는 숫자는 5입니다.

2. 5를 두 번 사용했을 때 만들 수 있는 숫자들은 다음과 같습니다.

• 5를 두 번 붙여서 만든 수 : 55
• 5 + 5 = 10
• 5 - 5 = 0
• 5 * 5 = 25
• 5 / 5 = 1

이어 붙여서 만든 숫자를 제외한 나머지 숫자들은 다음과 같은 방법으로 만들어진 것을 확인할 수 있습니다.

3. 5를 세 번 사용했을 때 만들 수 있는 수는 다음과 같습니다.

Set 자료구조로 만든 배열 각각의 인덱스를 N의 사용 횟수 라고 정합니다.

Set<Integer>[] set = new Set[9];
for (int i = 1; i < set.length; i++) {
    set[i] = new HashSet<>();
}

N을 i 번 사용했을 때 만들어지는 모든 경우의 숫자를 계산에 중복이 없는 Set 에 넣습니다.

for (int j = 1; j <= i / 2; j++) {
    Iterator<Integer> iter1 = set[j].iterator();

    while (iter1.hasNext()) {
        int val1 = iter1.next();

        Iterator<Integer> iter2 = set[i - j].iterator();
        while (iter2.hasNext()) {
            int val2 = iter2.next();

            set[i].add(val1 + val2);
            set[i].add(val1 - val2);
            set[i].add(val1 * val2);
            if (val2 != 0)
                set[i].add(val1 / val2);

            set[i].add(val2 - val1);
            set[i].add(val2 * val1);
            if (val1 != 0)
                set[i].add(val2 / val1);
        }
    }
}

위 코드에서는 j 번 사용했을 때 만들어진 숫자와 i - j 번 사용했을 때의 숫자의 위치를 바꾸어 -, *, / 연산을 진행하고, 따라서 j 는 굳이 i 번까지 다 순회할 필요가 없게 됩니다.

코드

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

public class Main {
    public static int solution(int N, int number) {
        Set<Integer>[] set = new Set[9];
        for (int i = 1; i < set.length; i++) {
            set[i] = new HashSet<>();
        }

        set[1].add(N);
        for (int i = 2; i < set.length; i++) {
            String tmp = "";

            for (int j = 0; j < i; j++)
                tmp += N;

            set[i].add(Integer.parseInt(tmp));

            for (int j = 1; j <= i / 2; j++) {
                Iterator<Integer> iter1 = set[j].iterator();

                while (iter1.hasNext()) {
                    int val1 = iter1.next();

                    Iterator<Integer> iter2 = set[i - j].iterator();
                    while (iter2.hasNext()) {
                        int val2 = iter2.next();

                        set[i].add(val1 + val2);
                        set[i].add(val1 - val2);
                        set[i].add(val1 * val2);
                        if (val2 != 0)
                            set[i].add(val1 / val2);

                        set[i].add(val2 - val1);
                        set[i].add(val2 * val1);
                        if (val1 != 0)
                            set[i].add(val2 / val1);
                    }
                }
            }
        }

        for (int i = 1; i <= 8; i++) {
            if (set[i].contains(number)) {
                return i;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int N = 1;
        int number = 1121;

        solution(N, number);
    }
}