[DP] N으로 표현 - JAVA (version 2)

이전에 한 번 풀고 풀이까지 작성한 적 있는 문제인데 다시 풀려니까 기억이 안난다,,,😳

내 풀이 참고하려고 글을 봤는데 또 성의없게 적혀 있다,,,😠

그래서 좀 더 꼼꼼하게 적어보고 풀면서 알아낸 것도 써보고자 다시 풀이를 적는다..!

 

[문제]

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

프로그래머스

 

[이전 풀이]

https://yummy0102.tistory.com/393

[DP] N으로 표현 - JAVA

---

🤔 기본 자료구조 결정 및 가정 조건

우선 이 문제는 DP 문제인 만큼 이전 연산을 기록해둬야 한다!

따라서 연산을 기록하기 위한 자료구조로 HashSet 을 선택했다!

HashSet은 중복을 허용하지 않기 때문에, 만약 연산의 결과가 같더라도 한번만 저장되어 메모리를 절약할 수 있다!

 

예를 들어 N=2 라고 가정해보자

그러면 N을 2번 사용해서 만들 수 있는 숫자는 다음과 같다

• 22
• 2 + 2 = 4
• 2 * 2 = 4
• 2 - 2 = 0
• 2 / 2 = 1

만약 이 숫자들을 배열에 저장한다면 [22, 4, 4, 0, 1] 처럼 같은 숫자가 중복되어 저장된다

그러나 문제에서는 주어진 숫자(number)를 N을 최소한으로 사용했을 때 몇 개가 필요한지만 구하면 되므로, 굳이 같은 숫자를 중복으로 저장할 필요가 없다!

 

따라서 HashSet 배열을 통해 저장할 것이다!

이 때 set[index]는 숫자 N을 index만큼 사용해서 구할 수 있는 숫자들이 저장된다

 

예를 들어 N=2 라고 가정하면

 

• set[1] = [2]
• set[2] = [22, 2+2, 2-2, 2*2, 2/2]
• set[3] = [222, 2+22, 2-22, 22-2, 2*22, ...]

 

이런식으로 저장되는 것이다!

(여기서 hashset이니까 중복되는 연산 결과는 저장되지 않고, 나누기 연산 시 0으로 나누는 것에 대한 예외처리 또한 필요하다!)

---

 

🤔 반복문 제한 조건

자 그럼 이제 반복을 몇 번, 그리고 어떻게 해야 할지가 남아있다!

여기서 문제에서 주어진 조건을 적극 활용해야 한다!

 

위는 문제에서 제시한 제한 사항이다

마지막을 보면 '최솟값이 8보다 크면 -1을 리턴한다' 고 되어있다

 

그말인 즉슨? 주어진 number를 만들기 위해 N이 8번 보다 많이 필요하다면 굳이 계산하지 않고 바로 -1을 리턴하면 된다는 것이다!

따라서 반복문은 최대 8번까지만 수행하도록 하면 된다!

---

 

🤔 반복문 수행 조건

그러면 set에 저장할 숫자들을 구하기 위해 반복문을 어떻게 수행해야 할까?

 

앞에서 말했듯이 set[index]에는 N을 index 만큼 사용해서 구할 수 있는 모든 연산 결과들이 저장되어야 한다

 

그러면 예를 들어서 생각해보자

N = 2이라고 가정했을 때 set[index] 에 저장될 결과를 작성해보자!

 

1) 먼저 set[1]에는 N을 1번만 사용해서 구할 수 있는 결과니까 [2] 하나만 저장된다

• set[1] = [2]

 

2) set[2]에는 N을 2번 사용해서 구할 수 있는 결과니까 우선 [22]는 기본으로 저장된다

그리고 N 한개인 2를 사칙연산하여 구할 수 있는 결과도 저장되어야 한다

• 2 + 2
• 2 - 2
• 2 * 2
• 2 / 2

그럼 최종적으로 set[2]에는 다음과 같은 결과값이 저장된다 -> 중복 결과값 제외

• set[2] = [22, 4, 0, 1]

 

3) 다음으로 set[3]에는 N을 3번 사용해서 구한 결과가 저장되니까, 우선 [222]는 기본으로 저장된다

그리고 set[1]과 set[2]의 연산 결과를 저장해도 된다

set[1]은 N이 1개, set[2]는 N이 2개가 사용된 것이므로, 이 들을 연산하면 총 N이 3번 사용되게 되는 것이다!

• set[1][0] & set[2][0] = (2+22), (2-22), (22-2), (2*22), (2/22), (22/2)
• set[1][0] & set[2][1] = (2+4), (2-4), (4-2), (2*4), (2/4), (4/2)
• ...

 

즉, 각 set[index]에는 기본적으로 연산하지 않고 index만큼 N을 이어붙인 숫자가 저장된다

이후 이중 반복문이라고 생각했을 때, set[i] = set[j] 와 set[i-j] 의 연산 결과가 저장되는 것이다!

 

자, 이제 코드를 보면 이해하기 쉬울 것이다!!

---

[자바 코드]

public class DP1 {
    public static void main(String[] args) {
        int N = 5;
        int number = 12;
        System.out.println(solution(N, number));
    }

    public static int solution(int N, int number) {
        int answer = -1;
        int now = N;
        Set<Integer>[] setArr = new HashSet[9];
        for (int i = 1; i < 9; i++) {
            setArr[i] = new HashSet<>();
            setArr[i].add(now);
            now = now * 10 + N;
        }

        for (int i = 1; i < 9; i++) {
            for (int j = 1; j < i; j++) {
                for (Integer a : setArr[j]) {
                    for (Integer b : setArr[i - j]) {
                        setArr[i].add(a + b);
                        setArr[i].add(a - b);
                        setArr[i].add(b - a);
                        setArr[i].add(a * b);
                        if (a != 0) {
                            setArr[i].add(b / a);
                        }
                        if (b != 0) {
                            setArr[i].add(a / b);
                        }
                    }
                }
            }
        }

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

사실 코드는 이전 풀이와 동일하다😅

중요한건? 풀이를 이해하고 나중에 봐도 기억하도록 자세하게 적었다는 것이다..!

 

---

아 그리고 고민했던 부분이 있다!

문제 조건에서 number는 0이 아닌 양수로 주어지는데, 빼기 연산을 하게 되면 0이나 음수가 발생한다

이를 set 배열에 저장하기 전에 if/else 조건을 통해 분기해서 저장해볼까..? 하는 생각을 했다!

그러면 필요없는 연산의 수도 줄고 메모리도 절약할 수 있을 것이라고 생각했다!!

 

백문이 불여일견,,,

바로 적용한 코드와 결과를 확인해보자!

 

우선 다음은 분기 조건을 적용하지 않은 위의 코드의 결과이다

 

 

다음은 분기 조건을 적용한 코드 부분과 결과이다!

        for(int i=1;i<9;i++) {
            for(int j=1;j<i;j++) {
                for(Integer a : setArr[j]) {
                    for(Integer b : setArr[i-j]) {
                        setArr[i].add(a+b);
                        setArr[i].add(a*b);
                        
                        if (a > b) {
                            setArr[i].add(a-b);
                        } else {
                            setArr[i].add(b-a);
                        }
                        
                        if (a != 0) {
                            setArr[i].add(b/a);
                        }
                        if (b != 0) {
                            setArr[i].add(a/b);
                        }
                    }
                }
            }
        }

 

결과값은 아래와 같다!

흠,,, 비슷하긴 한데 분기 조건을 추가한 코드가 조오금 더 빠른 걸 볼 수 있다!

 

사실 이거를 적기 전까지만 해도 분기 조건을 추가한 코드가 더 느려서 이상하다,, 했는데

막상 쓰면서 다시 돌려보니까 적용한게 더 빠르네..?😳😅

 

암튼! 조건을 적용하면 좋을 것 같다!

그럼 안녕~