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

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

코딩테스트 연습 - N으로 표현

 

---

 

풀이

dp[i]를 'N을 i번 사용하여 만들 수 있는 숫자들의 집합'이라고 정의합니다.

일단, 보기처럼 N=5일 경우, 5, 55, 555, ... , 55555555와 같이 '붙여 만드는 값'은 사칙연산으로 만들어지지 않기에 대응되는 dp[i]에 넣어줍니다.

dp[i] = (j는 1부터 i-1까지) (dp[j]의 원소)와 (dp[i-j]의 원소)의 사칙연산으로 모든 원소를 만들 수 있습니다.

i = 2부터 8까지 반복문을 돌면서 차근차근히 모든 원소를 찾아줍니다.

이후 numbers가 있는 가장 작은 set을 찾아 해당 set의 index를 return하면 됩니다: 없으면 -1을 return하면 됩니다.

 

효율적인 구현

0 이하의 값은 안 넣어도 됩니다: 5 + (5-5) = 5와 같은 느낌?

i에 대한 반복문에서, dp[i]를 완성하고 바로 numbers가 있는지 확인하여 있으면 코드를 종료시키는 게 더 효율적입니다.

 

배운 점

Set을 이용한 dp가 그렇게 생소한 개념은 아니었는데, 나는 괜히 시간 복잡도가 터지는 줄 알고 '잘 모르겠다~'하고 풀이를 봤다. 잘 생각했어야 하는데...

 

코드

import java.util.*;
 
class Solution {
    public int solution(int N, int number) {
        HashSet<Integer>[] dp = new HashSet[9];
        for (int i = 1; i <= 8; i++) {
            dp[i] = new HashSet<>();
        }
        int x = N;
        for (int i = 1; i < 9; i++) {
            dp[i].add(x);
            x*=10;
            x+=N;
        }
        for (int i = 1; i < 9; i++) {
            for (int j = 1; j < i; j++) {
                int k = i - j;
                if (j > k) continue;
                for (int a: dp[j]) {
                    for (int b: dp[k]) {
                        dp[i].add(a+b);
                        // 0은 의미가 없음
                        if (a > b) {
                            dp[i].add(a-b);
                        }
                        else if (a < b) {
                            dp[i].add(b-a);
                        }
                        dp[i].add(a*b);
                        // But, 1은 의미가 있음
                        if (a >= b) {
                            dp[i].add(a/b);
                        } else {
                            dp[i].add(b/a);
                        }
                    }
                }
            }
            if (dp[i].contains(number)) {
                return i;
            }
        }
        return -1;
    }
}