프로그래머스 코딩테스트 연습 : N으로 표현 Java 풀이 (DP 방식)

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

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

오랜만에 프로그래머스 문제를 풀었다.

약 1년 전에 풀다가 못 풀겠어서 포기했던 문제인데, 오늘 드디어 풀었다!

 

Solution

1. N과 number 가 같은 경우, 1을 리턴해야 한다. (TC 9번)

2. 최대로 쓸 수 있는 N의 갯수가 8이므로, 1번부터 8번까지 표현할 수 있도록 Integer 를 담는 Set 배열을 9 크기로 만들어준다. 무슨 말이냐면,

set[1] => N을 1개 썼을 때 나올 수 있는 숫자들

set[2] => N을 2개 썼을 때 나올 수 있는 숫자들

 

이라는 말이다.

 

3. N을 여러개 이어서 붙이는 것, 즉 예시에서는 5를 2개 붙인 숫자인 55 가 있었다. 이미 계산된 결과의 앞, 뒤에 N을 붙이는 경우는 고려하지 않는다.

예를 들어, set[2] 에 5*5 해서 25 가 있을 텐데, 255 나 525 같은 방식은 고려하지 않는다는 것이다. 그러므로, set[8] 까지 5, 55, 555, 5555.... 만 생각하면 된다.

 

4. 마지막으로, set[i-1] 번째의 숫자들에 N을 사칙연산으로 붙여주면 TC 5번부터 8번까지 해결할 수 없다. 왜냐면, 이는 결국

set[i] = N을 i-1번 써서 만들 수 있는 숫자들 ( 사칙연산자 ) N

이라는 것인데, 괄호를 고려해야 한다.

만약, i가 4이라면 위의 경우에서는

(5+5+5)+5

의 경우만 고려한다는 것이다. 

우리가 고려해야 할 경우는

(5+5+5)+5

5 + (5+5+5)

(5+5) + 5 + 5

5 + (5+5) + 5

5 + 5 + (5 + 5)

 

즉, set[i] = set[i-1] (사칙연산) set[1] +  set[i-2] (사칙연산) set[2] + ... +  set[2] (사칙연산) set[i-2]+  set[1] (사칙연산) set[i-1]

 

이다.

 

5. 주의해야 할점은, 같은 숫자들이 엄청나게 많아질 수 있다는 것이다. 메모리 초과가 날 수도 있다. set[2] 에 11 이 여러 개 있다면, 그 수에 대한 사칙연산 결과는 모두 똑같으므로 비효율적이다. 즉 중복 제거가 필요하므로, set 을 이용하는 것이다.

 

Source Code

import java.util.*;

public class Solution {
    public int solution(int N, int number) {
        if(N == number) {
            return 1;
        }
        TreeSet<Integer>[] possibleNumbers = new TreeSet[9];
        for(int i = 1; i <= 8; i++) {
            possibleNumbers[i] = new TreeSet<>();
        }
        possibleNumbers[1].add(N);
        for(int i = 2; i <= 8; i++) {
            String nn = "";
            for(int o = 0; o < i; o++) {
                nn += N;
            }
            possibleNumbers[i].add(Integer.parseInt(nn));
            if(Integer.parseInt(nn) == number) {
                return i;
            }
            for(int k = 1; k < i; k++) {
                Iterator<Integer> kIter = possibleNumbers[k].iterator();
                Iterator<Integer> pIter = possibleNumbers[i-k].iterator();
                while (kIter.hasNext()) {
                    Integer n1 = kIter.next();
                    HashSet<Integer> possibles = new HashSet<>();
                    while (pIter.hasNext()) {
                        Integer n2 = pIter.next();
                        possibles.add(n1 + n2);
                        possibles.add(n1 - n2);
                        possibles.add(n1 * n2);
                        if(n2 != 0) {
                            possibles.add(n1 / n2);
                        }
                    }
                    if(possibles.contains(number)) {
                        return i;
                    }
                    possibleNumbers[i].addAll(possibles);
                    pIter = possibleNumbers[i-k].iterator();
                    //이거 중요한데,kIter 를 돌면서 pIter를 한번 다 썼으므로 다시 초기화해야한다.
                }
            }
        }
        System.out.println(Arrays.toString(possibleNumbers));
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution_N으로표현().solution(4, 17));
        //System.out.println(new Solution_N으로표현().solution(2, 11));
    }
}