프로그래머스 - N으로 표현(Java)

문제 설명

숫자 N과 목표 숫자 number가 주어진다.

N을 여러 번 사용하여 사칙연산을 수행하고, number를 만들기 위해 필요한 N의 최소 사용 횟수를 구하는 문제이다.

다음 사칙연산을 사용한다.

+
-
*
/

N을 여러 번 이어 붙여 하나의 숫자로 사용할 수도 있다.

예를 들어 N = 5라면,

5
55
555
5555
...

처럼 사용할 수 있다.

단, N은 최대 8번까지만 사용할 수 있다.

---

예시

N = 5
number = 12

라고 하면,

5 + 5 + (5 / 5) + (5 / 5)

처럼 여러 가지 방법으로 12를 만들 수 있다.

이때 사용한 5의 개수 중 최소값을 찾아야 한다.

---

접근 방법

"N을 몇 개 사용했을 때 어떤 숫자들을 만들 수 있는가?"

를 저장한다.

예를 들어 N = 5라면,

N을 1개 사용

5

N을 2개 사용

55
5 + 5 = 10
5 - 5 = 0
5 * 5 = 25
5 / 5 = 1

따라서

{55, 10, 0, 25, 1}

과 같은 숫자를 만들 수 있다.

이렇게 계속 확장해 나간다.

---

countList는 "N을 몇 개 사용했는지"에 따라 만들 수 있는 숫자들을 저장하는 리스트이다.

---

풀이 순서

1. List<Set<Integer>>를 생성한다.
2. 1부터 8까지 각각의 Set을 만든다.
3. countList.get(1)에 N을 저장한다.
4. N을 2개 사용하는 경우부터 숫자를 만들어 나간다.
5. 이전에 만들어 놓은 숫자들을 사칙연산으로 조합한다.
6. N을 이어 붙인 숫자(55, 555 등)도 추가한다.
7. number가 어느 Set에 처음 등장하는지 확인한다.
8. 해당 Set의 번호를 반환한다.
9. 8번 안에 만들 수 없다면 -1을 반환한다.

---

최종 코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {

        List<Set<Integer>> countList = new ArrayList<>();

        // 0~8번 Set 생성
        for (int i = 0; i < 9; i++) {
            countList.add(new HashSet<>());
        }

        // N을 1개 사용해서 만들 수 있는 숫자
        countList.get(1).add(N);

        // N을 2개~8개 사용하는 경우
        for (int i = 2; i < 9; i++) {

            Set<Integer> countSet = countList.get(i);

            // N의 사용 개수를 나누어 조합
            for (int j = 1; j < i; j++) {

                Set<Integer> preSet = countList.get(j);
                Set<Integer> postSet = countList.get(i - j);

                // 두 Set의 모든 숫자를 조합
                for (int preNum : preSet) {
                    for (int postNum : postSet) {

                        countSet.add(preNum + postNum);
                        countSet.add(preNum - postNum);
                        countSet.add(preNum * postNum);

                        if (postNum != 0) {
                            countSet.add(preNum / postNum);
                        }
                    }
                }
            }

            // N을 이어 붙인 숫자 추가
            countSet.add(
                Integer.parseInt(String.valueOf(N).repeat(i))
            );
        }

        // number가 처음 등장하는 Set의 번호 반환
        for (Set<Integer> sub : countList) {
            if (sub.contains(number)) {
                return countList.indexOf(sub);
            }
        }

        // 8개를 사용해도 만들 수 없는 경우
        return -1;
    }
}

---

실행결과