Table of contents

프로그래머스 N으로 표현

number를 N과 사칙 연산만으로 만들 수 있는 조합 중, N의 사용횟수가 최소인 경우를 찾는 문제이다.

첫 번째 풀이

DP는 처음이라 우선 완전 탐색을 이용해서 풀어봤다. DP에 분류된 문제지만, 효율성 검사를 하지 않아서 테스트를 통과한다.

@Test
public void test() {
    assertThat(solution(5, 12)).isEqualTo(4);
    assertThat(solution(2, 11)).isEqualTo(3);
    assertThat(solution(5, 31168)).isEqualTo(-1);
}

int result = Integer.MAX_VALUE;
int[] nnn;

public int solution(int N, int number) {
    result = -1;
    nnn = new int[8];
    for (int i = 0; i < 8; i++) {
        nnn[i] = Integer.parseInt(Integer.toBinaryString((int) Math.pow(2, i + 1) - 1)) * N;

    }
    dfs(0, 0, number);
    return result;
}

public void dfs(int count, int num, int number) {
    if (count > 8)
        return;
    if (num == number) {
        if (count < result || result == -1) {
            result = count;
        }
        return;
    }

    for (int i = 0; i < 8; i++) {
        int NN = nnn[i]; // 5, 55, 555, 5555 ..
        int countN = i + 1; // 1, 2, 3, 4 ....

        // 0 +-*/ 5 -> ..... -> 0 +-*/ 55555555
        // (0 + 5): 5 +-*/ 5 -> ..... -> 5 +-*/ 55555555
        // (5 + 5): 10 +-*/ 5 -> ..... -> 10 +-*/ 55555555
        // (5 / 5): 1 +-*/ 5 -> ..... -> 1 +-*/ 55555555
        // ...........
        dfs(count + countN, num + NN, number);
        dfs(count + countN, num - NN, number);
        dfs(count + countN, num * NN, number);
        dfs(count + countN, num / NN, number);
    }
}

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

위의 제한사항 덕분에 N을 8번 사용했음에도 결과를 구할 수 없다면 탐색을 종료할 수 있게 된다.

두 번째 풀이

각 수행 과정에서 (계산식, 결과값) 을 미리 저장해놓고 다음 단계에서 재활용할 수 있을까 하다가, 복잡해서 포기했다. 결국 다른 사람의 풀이를 가져와서 디버깅으로 분석만 해봤다.

public int solution(int N, int number) {
    int answer = -1;
    HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
    HashSet<Integer> s = new HashSet<>();
    s.add(N);
    map.put(1, s);

    loop : for (int i = 2; i < 9; i++) {
        HashSet<Integer> set = new LinkedHashSet<>();

        int NNN = Integer.parseInt(Integer.toBinaryString((int) Math.pow(2, i) - 1)) * N;

        if (NNN == number){
            return i;
        }

        set.add(NNN);

        for (int j = 1; j <= i / 2; j++) {
            Iterator<Integer> it1 = map.get(j).iterator();
            Iterator<Integer> it2 = map.get(i - j).iterator();

            while (it1.hasNext()) {
                int itValue1 = it1.next();
                while (it2.hasNext()) {
                    int itValue2 = it2.next();
                    for (Operator o : Operator.values()) {
                        int calculate = o.calculate(itValue1, itValue2);
                        if (calculate == number){
                            answer = i;
                            break loop;
                        }

                        set.add(calculate);
                    }
                }
            }
        }
        map.put(i, set);
    }

    return answer;
}

enum Operator {
    PLUS {
        @Override
        public int calculate(int i, int j) {
            return i + j;
        }
    }, MINUS {
        @Override
        public int calculate(int i, int j) {
            return i - j;
        }
    }, BACKMINUS {
        @Override
        public int calculate(int i, int j) {
            return j - i;
        }
    }, MUL {
        @Override
        public int calculate(int i, int j) {
            return i * j;
        }
    }, DIV {
        @Override
        public int calculate(int i, int j) {
            if (j == 0){
                return 0;
            }
            return i / j;
        }
    }, BACKDIV {
        @Override
        public int calculate(int i, int j) {
            if (i == 0){
                return 0;
            }
            return j / i;
        }
    };

    public abstract int calculate(int i, int j);
}

굉장히 복잡해보이는데, 천천히 분석해보면 은근히 이해하기 쉬운 코드임을 알 수 있다.

loop : for (int i = 2; i < 9; i++) {

먼저 N을 8번 사용할 때까지 탐색하는 조건은 첫 번째 풀이와 같다. 앞에 붙은 loop : for 구문은 처음보는데, 중첩 반복문에서 자신을 포함하여 외부 반복문을 한번에 종료시킬 수 있는 구문인 듯 하다.

HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
HashSet<Integer> s = new HashSet<>();
s.add(N);
map.put(1, s);

map은 다음 단계에서 재사용하기 위해 각 단계에서 계산된 결과가 저장되는 (N의 사용 횟수, [계산 결과 목록]) 형태의 컬렉션이다. N을 한 번 사용하는 경우는 숫자 N밖에 없으므로 미리 저장하고 시작한다.

loop : for (int i = 2; i < 9; i++) {
    HashSet<Integer> set = new LinkedHashSet<>();

    int NNN = Integer.parseInt(Integer.toBinaryString((int) Math.pow(2, i) - 1)) * N;

    if (NNN == number){
        return i;
    }

    set.add(NNN);
    ///....
}

loop : for는 앞에서 설명한 것과 같다. i는 N을 사용한 횟수이며, NNN이라는 변수로 N, NN, NNN를 계산하여 저장한다. 예를 들어 N이 2라면 NNN은 22, 222, 2222, 22222...... 가 된다. NNN이 찾고자 하는 숫자라면 i를 반환하고 아니라면 NNN을 해당 단계의 DP 컬렉션에 넣고 탐색을 시작한다. 이렇게 시작하는 이유는 22, 222 같은 NNN은 해당 단계에서 사칙 연산을 수행하지 않고 N을 i번 사용한 결과이기 때문이다.

for (int j = 1; j <= i / 2; j++) {
    Iterator<Integer> it1 = map.get(j).iterator();
    Iterator<Integer> it2 = map.get(i - j).iterator();
    // .....
}

예를 들어 현재 N을 사용한 횟수 i가 5라면 (i = 1 +-/ i = 4), (i = 2 +-/ i = 3) 즉, 1단계와 4단계에서 계산된 결과에 각각 사칙연산을 수행하면 5단계의 결과가 된다. 마찬가지로 2단계와 3단계에서 계산된 결과에 각각 사칙연산을 수행하면 5단계의 결과가 된다. (2, 3)과 (3, 2)에서 사칙연산의 결과는 같을 것이기 때문에 중복을 피하기 위해 i / 2 까지만 수행한다.

주의할 점은 a와 b의 사칙연산에서 교환법칙이 성립하지 않는 경우를 고려해야 한다는 점이다. 그렇기 때문에 Operation 에서는 4개의 사칙 연산과 교환법칙이 성립하지 않는(뺄셈, 나눗셈) 2개의 BACKMINUS, BACKDIV 연산까지 수행한다.

while (it1.hasNext()) {
    int itValue1 = it1.next();
    while (it2.hasNext()) {
        int itValue2 = it2.next();
        for (Operator o : Operator.values()) {
            int calculate = o.calculate(itValue1, itValue2);
            if (calculate == number){
                answer = i;
                break loop;
            }

            set.add(calculate);
        }
    }
}

다시 본론으로 돌아와서 (i = 1 +-*/ i = 4, i = 4 -/ i = 1) 와 같은 공식이 성립되는 이유를 살펴보자.

  • N = 2
  • i = 1
    • 2 (N)
  • i = 2
    • 22 (NN)
    • (i = 1 +-*/ i = 1, i = 1 -/ i = 1)
    • 1단계와 1단계의 결과에 6개의 연산을 수행
    • 2 + 2 = 4
    • 2 - 2 = 0
    • 2 * 2 = 4
    • 2 / 2 = 1
    • 2 - 2 = 0 (BACKMINUS, 중복)
    • 2 / 2 = 1 (BACKDIV, 중복)
  • i = 3
    • 222 (NNN)
    • (i = 1 +-*/ i = 2, i = 2 -/ i = 1)
    • 1단계와 2단계의 결과에 6개의 연산을 수행
    • 2 + 22(NN) = 24, 2 - 22(NN) = -20, 2 * 22(NN) = 44, 2 / 22(NN) = 0, 22(NN) - 2 = 20, 22 / 2 = 11
    • 2 + (2 + 2 = 4) = 6, 2 - (2 + 2 = 4) = -2, 2 * (2 + 2 = 4) = 8, 2 / (2 + 2 = 4) = 0, (2 + 2 = 4) - 2 = 2, (2 + 2 = 4) / 2 = 2
    • ........
    • 2 +-*/ (2 * 2 = 4), (2 * 2= 4) -/ 2
    • 2 +-*/ (2 / 2 = 0), (2 / 2 = 0) -/ 2
    • BACKMINUS, BACKDIV는 중복이라 생략

3단계 까지만 살펴봐도 충분히 이해할 수 있으리라 생각한다. 첫 번째 풀이에서 사용한 완전 탐색의 경우 i = 3 이고, 2 + (2 + 2) 와 같은 식에서 i = 2 에서 계산된 (2 + 2) 를 i = 3에서 다시 계산하게 된다. 반면 DP를 사용하면 (2 + 2)가 아닌 계산된 4와 연산을 수행하기 때문에 계산 과정이 훨씬 줄어든다.

수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.

만약 수식에 괄호를 사용할 수 없다면 이 방법은 불가능하다.

첫번째 풀이 두번째 풀이
29 ms ~ 48 ms 1 ms ~ 22 ms

비록 효율성 테스트를 수행하지는 않지만 완전 탐색과 DP의 효율성 차이가 많이 나는 것을 알 수 있다.