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

문제 링크

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

 

문제 요약

백준 아니고 프로그래머스라서 패스

 

입력

백준 아니고 프로그래머스라서 패스

 

출력

백준 아니고 프로그래머스라서 패스

 

접근법

DP를 쓰면 쉽게 풀 수 있는 문제. 물론 난 너무 어렵게 생각하다가 구글링 해서 풀었다.

 

근데 사실상 말이 DP지, 브루트포스에 가깝다. x개의 N으로 만들 수 있는 숫자를 전부 만들어서, 주어진 number와 동일한지 확인을 해야하기 때문이다. 그래서 DP가 아닌건가? 하고 좀 고민을 하다가, 문제에

 최솟값이 8보다 크면 -1을 return 합니다.

라는 조건을 보고, DP로 숫자를 전부 만드는 방식이 맞는 것 같다고 확신했다. 숫자가 겁나게 많아지는 상황을 막는 조건이라고 판단했기 때문이다. 그런데도 풀이 과정 자체는 그냥 브루트포싱을 하는데 DP로 살짝 최적화를 곁들인 느낌이긴 했다.

 

문제 해결의 핵심 원리는 이것 하나이다.

x개의 N의 사칙연산으로 만들 수 있는 숫자는 다음과 같다. ({}은 집합, *는 사칙연산을 의미하는 임의의 연산자, U는 합집합)

{1개의 N으로 만들 수 있는 숫자} * {x - 1개의 N으로 만들 수 있는 숫자} U
{2개의 N으로 만들 수 있는 숫자} * {x - 2개의 N으로 만들 수 있는 숫자} U
...
{x - 2개의 N으로 만들 수 있는 숫자} * {2개의 N으로 만들 수 있는 숫자} U
{x - 1개의 N으로 만들 수 있는 숫자} * {1개의 N으로 만들 수 있는 숫자} U
{5를 x개 이어붙인 숫자 (55...555, 5의 개수가 x개)}

 

사칙연산중 빼기(-)와 나누기(/)는 교환법칙이 성립하지 않기 때문에, 다음과 같음을 주의해야 한다.

{1개의 N으로 만들 수 있는 숫자} * {x - 1개의 N으로 만들 수 있는 숫자} 집합과
{x - 1개의 N으로 만들 수 있는 숫자} * {1개의 N으로 만들 수 있는 숫자} 집합은 동일한 집합이 아니다!

물론 더하기(+)와 곱하기(*)는 교환법칙이 성립해서 겹치는 숫자가 나오기 때문에, 코드에서 최적화를 하면 이 부분에서 연산을 한개라도 더 줄일 수 있긴 한데, 어차피 구현할 때 겹치는 숫자가 나오는 것을 방지해서 HashSet을 사용했기 때문에 그냥 쿨하게 넘겨준다.

 

알고리즘은 DP를 적용하여서, x개의 N의 사칙연산으로 만들 수 있는 숫자의 집합을 구하기 위해

{1개의 N의 사칙연산으로 만들 수 있는 수}, {2개의 N의 사칙연산으로 만들 수 있는 수}, ..., {x - 1개의 N의 사칙연산으로 만들 수 있는 수}의 집합을 이용하는 것이다.

 

추가적으로 최적화를 위해, x개의 N으로 number를 만들 수 있다는 것이 확인되는 순간 바로 프로그램을 종료하게 구현했다.

 

 

시간 복잡도

계산이 너무 어렵다....

HashSet을 사용했기 때문에, 두 집합 사이의 모든 숫자 사이에 사칙연산을 하는 데 걸리는 시간 외에는 추가적으로 드는 시간은 없다고 보면 된다.

8개의 N으로 만들 수 있는 수 까지만 찾아보면 되기 때문에 그리 오래 걸리지 않는다.

 

 

공간 복잡도

8개의 HashSet<Integer>에 대한 메모리가 필요.

HashSet은 실제 저장된 원소 이상의 공간이 필요하다는 것에 유의할 것.

 

 

풀면서 놓쳤던 점

x개의 N의 사칙연산으로 만들 수 있는 숫자는 다음과 같다. ({}은 집합, *는 사칙연산을 의미하는 임의의 연산자, U는 합집합)

{1개의 N으로 만들 수 있는 숫자} * {x - 1개의 N으로 만들 수 있는 숫자} U
{2개의 N으로 만들 수 있는 숫자} * {x - 2개의 N으로 만들 수 있는 숫자} U
...
{x - 2개의 N으로 만들 수 있는 숫자} * {2개의 N으로 만들 수 있는 숫자} U
{x - 1개의 N으로 만들 수 있는 숫자} * {1개의 N으로 만들 수 있는 숫자} U
{5를 x개 이어붙인 숫자 (55...555, 5의 개수가 x개)}

이 원리를 캐치하긴 했지만, 이걸 한번 더 꼬아서 생각해서 구현했더니 풀 수가 없었다.

 

예를 들어 7개의 N으로 만들 수 있는 숫자는

{3개의 N으로 만들 수 있는 숫자} * {3개의 N으로 만들 수 있는 숫자} * {1개의 N으로 만들 수 있는 숫자}도 있고

{5개의 N으로 만들 수 있는 숫자} * {2개의 N으로 만들 수 있는 숫자}도 있는데

이걸 어떻게 구현할까 한참 고민했다.

 

HashSet을 8 * 8개 만들고 막 별 짓을 다했는데, 위의 원리를 적용하면

6개의 N으로 만들 수 있는 숫자에 이미

{3개의 N으로 만들 수 있는 숫자} * {3개의 N으로 만들 수 있는 숫자}가 포함되어 있는, DP의 원리를 활용한 문제 풀이가 가능하다는 것을 뒤늦게 알았다.

 

어려운 문제가 아니었는데 여러모로 아쉽다.

 

 

이 문제에서 얻어갈 점

HashSet의 사용. DP.

 

 

코드

import java.util.HashSet;

class Solution {
    public int solution(int N, int number) {
        
        //이 부분은 뒤에서 따로 코드상 체크가 안되기 때문에 미리 검사해줌
        if (N == number)
            return 1;
        
        //DP에 활용할 HashSet. index는 index개의 N으로 만든 숫자라는 의미. 1 - 8만 사용할 것.
        HashSet<Integer>[] numbersMadeOfN = new HashSet[9];
        initNumbersMadeOfN(numbersMadeOfN, N); // set 초기화
        
        return canGenerateNumberWithNumOfN(numbersMadeOfN, number, N);
    }
    
    static int canGenerateNumberWithNumOfN(HashSet<Integer>[] numbersMadeOfN, int number, int N)
    {
        // N을 2개 쓰는 경우부터 체크
        for (int numOfN = 2; numOfN <= 8; numOfN++)
        {
            // {1} * {numOfN - 1} U {2} * {numOfN - 2} U ... 이 알고리즘을 구현한 부분. 
            for (int subNumOfN = 1; subNumOfN < numOfN; subNumOfN++)
                addNumbersMadeOfN(numbersMadeOfN[numOfN], numbersMadeOfN[subNumOfN], numbersMadeOfN[numOfN - subNumOfN]); //두 집합을 넘겨 받아서 사칙연산으로 숫자 만들어서 넣어주는 함수
            if (numbersMadeOfN[numOfN].contains(number)) //number가 들어있는지 체크. 들어있으면 바로 return
                return numOfN;
        }
        
        return -1; //최솟값이 8보다 큰 경우
    }
    
    //subset 2개를 받아서 사칙연산해서 숫자 만들어서 넣어주는 메소드.
    static void addNumbersMadeOfN(HashSet<Integer> numbersMadeOfN, HashSet<Integer> subset1, HashSet<Integer> subset2)
    {
        for (int num1 : subset1)
        {
            for (int num2 : subset2)
            {
                numbersMadeOfN.add(num1 + num2);
                numbersMadeOfN.add(num1 - num2);
                numbersMadeOfN.add(num1 * num2);
                if (num2 != 0)
                	numbersMadeOfN.add(num1 / num2);
            }
        }
    }
    
    static void initNumbersMadeOfN(HashSet<Integer>[] numbersMadeOfN, int N)
    {
        int num = N;
        for (int i = 1; i <= 8; i++)
        {
            numbersMadeOfN[i] = new HashSet<Integer>();
            numbersMadeOfN[i].add(num);
            num = num * 10 + N; //5를 n개 이어붙인 숫자 (5, 55, 555, ...)를 미리 넣어준다.
        }
    }
}