프로그래머스 - N으로 표현(02/02) (java)

1. 문제

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

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

문제 설명

제한 사항

입출력 예

11의 경우 22 / 2 = 11이므로 2를 3개 사용해서 만들 수 있다.

---

2. 어떻게 풀까?

• N으로 9개 이상 표현하면 표현할 수 없다는 것으로 보고 -1을 리턴한다.
• 그러므로 1개로 표현했을 때 만들 수 있는 값 ~ 8개로 표현했을 때 만들 수 있는 값에서 number와 같은 값이 있으면 리턴하도록 한다.
  1. N 1개를 사용했을 때 표현 가능한 숫자 - N
  2. N 2개를 사용했을 때 표현 가능한 숫자 - NN, (N 1개를 사용했을 때 표현 가능한 값) 사칙연산 (N 1개를 사용했을 때 표현 가능한 값)
  3. N 3개를 사용했을 때 표현 가능한 숫자 - NNN, (N 1개를 사용했을 때 표현 가능한 값) 사칙연산 (N 2개를 사용했을 때 표현 가능한 값) U (N 2개를 사용했을 때 표현 가능한 값) 사칙연산 (N 1개를 사용했을 때 표현 가능한 값)
     • NNN
     • N + NN, N - NN, N * NN, N / NN
     • N + (N+N), N - (N+N), N * (N+N), N / (N+N)
     • N + (N-N), N - (N-N), N * (N-N), N / (N-N)
     • N + (N*N), N -(N*N), N *(N*N), N /(N*N)
     • N + (N/N), N -(N/N), N *(N/N), N /(N/N)
     • NN + N, NN - N, NN * N, NN / N
     • (N+N) + N, (N+N) - N, (N+N) * N, (N+N) / N
     • (N-N) + N, (N-N) - N, (N-N) * N, (N-N) / N
     • (N*N) + N, (N*N) - N, (N*N) * N, (N*N) / N
     • (N/N) + N, (N/N) - N, (N/N) * N, (N/N) / N
  4. 덧셈과 곱셈은 교환 법칙이 성립하기 때문에, (1개 표현 수) 사칙연산 (2개 표현 수)와 (2개 표현 수) 사칙연산 (1개 표현 수)가 같지만, 뺄셈과 나눗셈은 성립하지 않기 때문에 다르다
     • 2 + 22 = 22 + 2 = 24, 2 * 22 = 22 * 2 = 44
     • 2 - 22 = -20, 22 - 2 = 20, 2 / 22 = 0, 22 / 2 = 11
  5. 그러므로 N x개를 사용했을 때 표현 가능한 숫자는 - N을 x번 붙힌 값, (N 1개 표현 수) (덧셈, 뺄셈, 역뺄셈, 곱셈, 나눗셈, 역나눗셈) (N x-1개 표현수) U (N 2개 표현 수) (덧셈, 뺄셈, 역뺄셈, 곱셈, 나눗셈, 역나눗셈) (N x-2개 표현수) U ... U (N x/2개 표현 수) (덧셈, 뺄셈, 역뺄셈, 곱셈, 나눗셈, 역나눗셈) (N x/2개 표현수) 이다.

---

3. 코드

테스트 코드

package doNotSolve.programmers.level3.N으로표현;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    assertThat(new Solution().solution(5, 12), is(4));
    assertThat(new Solution().solution(2, 11), is(3));
    assertThat(new Solution().solution(5, 5), is(1));
    assertThat(new Solution().solution(5, 10), is(2));
    assertThat(new Solution().solution(5, 31168), is(-1));
    assertThat(new Solution().solution(1, 1121), is(7));
  }

  @Test
  public void test2() {
    assertThat(new Solution().solution(5, 1010), is(7));
    assertThat(new Solution().solution(3, 4), is(3));
    assertThat(new Solution().solution(5, 5555), is(4));
    assertThat(new Solution().solution(5, 5550), is(5));
  }

  @Test
  public void test3() {
    assertThat(new Solution().solution(5, 20), is(3));
    assertThat(new Solution().solution(3, 30), is(3));
    assertThat(new Solution().solution(6, 65), is(4));
    assertThat(new Solution().solution(5, 2), is(3));
    assertThat(new Solution().solution(5, 4), is(3));
    assertThat(new Solution().solution(1, 1), is(1));
    assertThat(new Solution().solution(1, 11), is(2));
    assertThat(new Solution().solution(1, 111), is(3));
    assertThat(new Solution().solution(1, 1111), is(4));
    assertThat(new Solution().solution(1, 11111), is(5));
    assertThat(new Solution().solution(7, 7776), is(6));
    assertThat(new Solution().solution(7, 7784), is(5));
  }
}

실제 코드

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Map;

public class Solution {

  Map<Integer, HashSet<Integer>> calculationResultMap;

  public int solution(int N, int number) {
    calculationResultMap = new HashMap<>();

    for (int i = 1; i < 9; i++) {
      HashSet<Integer> calculationResults = getCalculationValues(i, N);
      if (calculationResults.contains(number)) {
        return i;
      }
      calculationResultMap.put(i, calculationResults);
    }

    return -1;
  }

  private HashSet<Integer> getCalculationValues(int count, int N) {
    HashSet<Integer> set = new LinkedHashSet<>();
    int attach = getAttachValue(count, N);
    set.add(attach);

    for (int j = 1; j <= count / 2; j++) {
      for (int a : calculationResultMap.get(j)) {
        for (int b : calculationResultMap.get(count - j)) {
          for (Operator op : Operator.values()) {
            set.add(op.calcuate(a, b));
          }
        }
      }
    }

    return set;
  }

  private int getAttachValue(int count, int N) {
    return Integer.parseInt(Integer.toBinaryString((int) Math.pow(2, count) - 1)) * N;
  }

}

enum Operator {
  PLUS {
    @Override
    public int calcuate(int a, int b) {
      return a + b;
    }
  },
  MINUS {
    @Override
    public int calcuate(int a, int b) {
      return a - b;
    }
  },
  BACKMINUS {
    @Override
    public int calcuate(int a, int b) {
      return b - a;
    }
  },
  MULTIPLY {
    @Override
    public int calcuate(int a, int b) {
      return a * b;
    }
  },
  DIVIDE {
    @Override
    public int calcuate(int a, int b) {
      return b == 0 ? 0 : a / b;
    }
  },
  BACKDIVIDE {
    @Override
    public int calcuate(int a, int b) {
      return a == 0 ? 0 : b / a;
    }
  };

  abstract int calcuate(int a, int b);
}

---

4. 느낀 점

• 처음 문제를 풀 때, N이 9개 이상이면 -1을 리턴하라고 해서 N 1개로 표현 가능한 식, 2개로 표현 가능한 식, ..., 8개로 표현 가능한 식을 Set에 담아서 그 식을 계산한 값이 number와 같으면 리턴하도록 코드를 작성하면 되겠구나 생각했다.
• 근데 처음 생각한 코드는, (N-N/N*NN+N) 같은 식은 괄호 위치에 따라 다르게 계산될 수 있는데 그걸 생각 못하고 앞에서부터 계산한 값만 생각했다. 그래서 계속 1번, 8번 테스트가 실패로 나왔다.
• 왜 틀렸는지 계속 생각해봐도 이해가 안 돼서 다른 사람들이 작성한 코드를 봤는데, 괄호 때문에 계산 순서가 달라질 수 있는 것을 고려하지 않은 점, 뺼셈과 나눗셈은 교환 법칙이 성립하지 않는 점을 생각하지 못해서 틀린 것 같다.
• 그 외에도 Enum을 사용해서 덧셈, 뺄셈, 역뺄셈, 곱셈, 나눗셈, 역나눗셈을 해결한 코드가 전혀 생각하지 못한 방법이라 똑같이 따라 해 보았다.
• 완전 탐색(DFS)을 이용하여 해결한 답도 많았는데, 해당 문제 카테고리가 DP(Dynamic Programming)이기도 했고, DFS를 이용하면 N*N-N/N 같은 식도 고려하지 않고 통과가 된다고 한다. 그래서 DFS는 따로 참고하지 않았다.