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

💡 문제
N으로 표현 (https://school.programmers.co.kr/learn/courses/30/lessons/42895)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

• 동적 프로그래밍 (Dynamic Programming): 이 문제는 동적 프로그래밍의 접근 방식을 사용하여 해결됩니다. 동적 프로그래밍은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법론으로, 각 부분 문제의 해결 방법을 저장하고 재활용함으로써 전체 문제를 해결합니다. 이러한 특성을 이용하여 중복 계산을 피하고 효율적인 알고리즘을 설계할 수 있습니다.
• 최적 부분 구조 (Optimal Substructure): 이 문제는 최적 부분 구조를 가지고 있습니다. 즉, 주어진 문제를 작은 부분 문제로 나누어 해결하는 것이 가능하며, 각 부분 문제의 최적해를 결합하여 전체 문제의 최적해를 찾을 수 있습니다.
• 수학적 사고와 추론: 이 문제를 해결하기 위해서는 숫자와 사칙연산에 대한 기본적인 수학적 이해와 추론이 필요합니다. 숫자를 조합하여 원하는 숫자를 만들기 위해서는 어떤 숫자와 연산을 사용해야 하는지에 대한 논리적 추론이 필요합니다.
• 자료 구조 (Data Structures): 이 문제를 해결하는데 필요한 자료 구조는 주로 배열과 집합(Set)입니다. 배열은 숫자의 조합을 저장하는 데 사용되며, 집합은 중복된 계산을 피하고 특정 숫자의 존재 여부를 확인하는 데 사용됩니다.

---

🤓 문제 풀이

🔨 문제 설명

 

---

🔨 접근 방법

1. 문제 이해: 먼저 문제의 요구사항을 이해하고, 입력과 출력 예시를 살펴봅니다. 주어진 숫자 N과 number를 사용하여 특정 숫자를 만드는데 필요한 최소한의 N 사용 횟수를 찾아야 합니다.
2. 문제 분해: 문제를 작은 단위로 분해하여 해결할 수 있는 부분 문제로 나눕니다. 이 경우, 숫자 N을 사용하여 만들 수 있는 모든 숫자의 조합을 찾고, 그 중에서 number를 만들 수 있는 최소한의 N 사용 횟수를 찾아야 합니다.
3. 알고리즘 선택: 주어진 문제는 동적 프로그래밍을 사용하여 해결할 수 있습니다. 동적 프로그래밍은 작은 부분 문제들을 해결하여 전체 문제를 해결하는 방식으로, 중복 계산을 피할 수 있고 효율적인 해결 방법을 제공합니다.

---

🔨 문제 풀이 과정

• 초기화: 가능한 N 사용 횟수에 따른 숫자 조합을 저장할 배열을 초기화합니다. 이 때, N을 1번부터 8번까지 사용하여 만들 수 있는 숫자의 조합을 저장합니다.
• 숫자 조합 계산: 초기화된 배열을 이용하여 숫자 조합을 계산합니다. 각 숫자 조합은 사칙연산을 사용하여 만들어지며, 중복된 계산을 피하기 위해 이미 계산된 숫자는 저장하여 재활용합니다.
• 해결: 주어진 number를 만들 수 있는지 확인하고, 만약 가능하다면 최소한의 N 사용 횟수를 반환합니다.

🔨 알고리즘 선택 이유

• 동적 프로그래밍의 효율성: 주어진 문제는 작은 부분 문제들을 해결하여 전체 문제를 해결하는데 적합한 문제입니다. 동적 프로그래밍을 사용하면 중복 계산을 피할 수 있고, 효율적인 해결 방법을 제공합니다.
• 최적 부분 구조: 주어진 문제는 작은 부분 문제들을 해결하여 전체 문제를 해결하는데 적합한 최적 부분 구조를 갖고 있습니다. 작은 부분 문제들의 해결 방법을 결합하여 전체 문제를 효율적으로 해결할 수 있습니다.

---

🔨 구현코드

6트만ㅇ...성공..

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        // 가능한 N 사용 횟수에 따른 숫자 조합을 저장하는 배열
        ArrayList<HashSet<Integer>> dp = new ArrayList<>();
        
        // N을 1번부터 8번까지 사용하여 만들 수 있는 숫자 초기화
        for (int i = 0; i < 8; i++) {
            dp.add(new HashSet<>());
            int num = Integer.parseInt(Integer.toString(N).repeat(i + 1));
            dp.get(i).add(num);
            
            // 만들어진 숫자가 number와 같다면 해당 사용 횟수 반환
            if (num == number) return i + 1;
        }
        
        // 숫자 조합을 계산하고 number를 만들 수 있는지 확인
        for (int i = 1; i < 8; i++) {
            for (int j = 0; j < i; j++) {
                for (int num1 : dp.get(j)) {
                    for (int num2 : dp.get(i - j - 1)) {
                        dp.get(i).add(num1 + num2);
                        dp.get(i).add(num1 - num2);
                        dp.get(i).add(num1 * num2);
                        if (num2 != 0) dp.get(i).add(num1 / num2);
                        
                        // 만들어진 숫자가 number와 같다면 해당 사용 횟수 반환
                        if (num1 + num2 == number || num1 - num2 == number || num1 * num2 == number || (num2 != 0 && num1 / num2 == number)) 
                            return i + 1;
                    }
                }
            }
        }
        
        // number를 만들 수 없는 경우 -1 반환
        return -1;
    }
}

---

📚 풀이 보완

코드 설명

성공한 코드와 이전에 실패한 코드의 주요 차이점과 수정된 로직 포인트 코드 설명

실패한 코드의 문제점과 수정 전략:

1. 초기화한 배열 dp에 대한 접근이 잘못되었습니다. 초기화된 dp 배열은 각 사용 횟수에 따라 만들 수 있는 숫자의 집합을 저장해야 합니다. 하지만 코드에서는 잘못된 인덱스를 사용하여 숫자를 저장하고 있었습니다.
2. 각 숫자 조합을 계산하는 부분에서 중복된 계산이 발생하고 있습니다. 이는 동일한 숫자 조합이 여러번 계산되고 있는 것입니다.
3. 숫자 조합을 계산하는 방식이 부족합니다. 현재 코드에서는 모든 사칙연산 조합을 고려하지만, 특정 숫자를 만드는 데 필요한 최소한의 N 사용 횟수를 고려하지 않았습니다.

성공한 코드의 수정된 로직 포인트:

1. 초기화된 배열 dp에 대한 접근이 수정되었습니다. 각 사용 횟수에 따라 숫자의 집합을 올바르게 저장하도록 수정되었습니다.
2. 숫자 조합을 계산하는 부분에서 중복된 계산을 피하고, 이미 만들어진 숫자가 number와 같은지 확인하여 최소 사용 횟수를 반환하도록 수정되었습니다.
3. 숫자 조합을 계산할 때, 특정 숫자를 만드는 데 필요한 최소한의 N 사용 횟수를 고려하여 수정되었습니다. 이를 통해 불필요한 계산을 줄일 수 있습니다.

요약

1. 초기화된 배열의 접근: 초기화된 배열 dp에 대한 접근이 잘못되었습니다. 각 사용 횟수에 따른 숫자의 조합을 저장하는 배열을 만들어야 했지만, 인덱스를 잘못 사용하여 숫자의 조합을 저장하고 있었습니다.
2. 중복된 계산: 중복된 계산이 발생했습니다. 각 숫자 조합을 계산할 때 중복된 계산을 피하지 않고 모든 사칙연산 조합을 고려하고 있었습니다.
3. 최적 부분 구조 고려 부족: 작은 부분 문제들의 해결 방법을 고려하지 않았습니다. 따라서 최적 부분 구조를 고려하지 않고 전체 문제를 해결하려고 시도했습니다.

이러한 이유로 이전의 코드는 올바른 결과를 반환하지 못했습니다. 이에 대한 수정된 코드는 초기화된 배열에 대한 접근을 수정하여 올바른 숫자의 조합을 저장하고, 중복된 계산을 피하며 최적 부분 구조를 고려하여 작은 부분 문제들을 해결하여 전체 문제를 해결하도록 수정되었습니다.

---

📍 Plus+

공간 복잡도 (메모리 공간의 양)

1. dp 배열: N을 사용하여 만들 수 있는 숫자의 조합을 저장하기 위한 배열이 필요합니다. 이 배열의 크기는 최대 8까지이며, 각 배열 요소는 HashSet으로 이루어져 있습니다. 따라서 dp 배열의 공간 복잡도는 O(8 * 2^8)입니다.
2. dp 배열은 가능한 N 사용 횟수에 따른 숫자의 조합을 저장하는데 사용됩니다. dp 배열의 크기는 사용할 수 있는 N의 최대 횟수인 8까지이며, 각 배열 요소는 HashSet으로 이루어져 있습니다. 따라서 dp 배열의 공간 복잡도는 O(8 * 2^8)입니다. 여기서 2^8은 각 N마다 만들 수 있는 숫자 조합의 최대 개수입니다.
3. HashSet: 각 dp 배열 요소는 HashSet을 포함하고 있습니다. HashSet은 저장된 요소에 대한 고유한 값만을 가지므로, 중복된 숫자를 방지하고 최적의 해결 방법을 찾을 수 있습니다. HashSet의 공간 복잡도는 O(n)입니다.
4. 각 dp 배열 요소는 HashSet을 포함하고 있습니다. HashSet은 중복된 숫자를 방지하고 최적의 해결 방법을 찾는데 사용됩니다. HashSet의 공간 복잡도는 저장된 요소의 개수에 비례하므로 O(n)입니다.

따라서 전체적인 공간 복잡도는 dp 배열에 의해 결정됩니다. 최종적으로 O(8 * 2^8)입니다.

시간복잡도 (알고리즘이 실행되는 동안 소요되는 시간)

1. 숫자 조합 계산: 주어진 문제에서는 가능한 모든 N 사용 횟수에 대한 숫자 조합을 계산해야 합니다. 이를 위해 중첩된 반복문을 사용하여 모든 가능한 조합을 계산합니다.
   • 외부 반복문은 N 사용 횟수에 대한 반복이며, 최대 8번 반복됩니다.
   • 내부 반복문은 각 N 사용 횟수에 대한 숫자 조합을 계산하는 반복문입니다. 이 내부 반복문에서는 HashSet을 사용하여 중복된 계산을 피하고, 모든 사칙연산 조합을 고려합니다.
   • 내부 반복문 내에서는 HashSet에 요소를 추가하고 확인하는 작업이 수행되며, HashSet의 시간 복잡도는 O(1)입니다.

따라서 전체적인 시간 복잡도는 외부 반복문과 내부 반복문에서 수행되는 작업의 시간 복잡도에 의해 결정됩니다. 내부 반복문에서의 각 작업은 상수 시간이 소요되므로, 시간 복잡도는 O(8 * (8^2 * 2^8))입니다.

 

요약

• 공간 복잡도 : O(8 * 2^8)
• 시간 복잡도 : O(8 * (8^2 * 2^8))

---

동적 프로그래밍 문제 파악

동적 프로그래밍은 주어진 문제를 작은 부분 문제로 나누고, 이를 해결하여 전체 문제를 해결하는 방식입니다. 이를 통해 중복 계산을 피하고, 효율적으로 문제를 해결할 수 있습니다.

주어진 문제에서 동적 프로그래밍을 사용할 수 있는 부분은 다음과 같습니다:

1. 작은 부분 문제 정의: 주어진 숫자 N을 사용하여 만들 수 있는 숫자의 조합을 계산합니다. 이때, 각 사용 횟수에 대한 숫자의 조합을 저장하는 배열을 만듭니다.
2. 부분 문제 해결: 작은 부분 문제들을 해결하여 전체 문제를 해결합니다. 각 숫자 조합을 계산할 때 중복된 계산을 피하고, 이미 계산된 숫자를 저장하여 재활용합니다.
3. 최적 부분 구조 활용: 최적 부분 구조를 고려하여 작은 부분 문제들의 해결 방법을 결합하여 전체 문제를 해결합니다. 각 숫자 조합을 계산할 때 최소한의 N 사용 횟수를 고려하여 최적의 해결 방법을 찾습니다.

이러한 방식으로 동적 프로그래밍을 사용하여 주어진 문제를 해결할 수 있습니다. 문제를 작은 단위로 나누고, 작은 부분 문제들을 해결하여 전체 문제를 해결하는 것이 핵심입니다.