Leetcode Java 24 Game

문제

Link

코드

class Solution {

  public boolean judgePoint24(int[] cards) {
    return this.dfs(new double[] { cards[0], cards[1], cards[2], cards[3] });
  }

  private boolean dfs(double[] cards) {
    int length = cards.length;
    if (length == 1) {
      return Math.abs(cards[0] - 24) < 0.001;
    }
    for (int i = 0; i < length; i++) {
      for (int j = i + 1; j < length; j++) {
        double[] temp = new double[length - 1];
        for (int k = 0, index = 0; k < length; k++) {
          if (k != i && k != j) {
            temp[index++] = cards[k];
          }
        }
        for (double d : this.compute(cards[i], cards[j])) {
          temp[temp.length - 1] = d;
          if (this.dfs(temp)) {
            return true;
          }
        }
      }
    }
    return false;
  }

  private double[] compute(double a, double b) {
    return new double[] { a + b, a - b, b - a, a * b, a / b, b / a };
  }

}

결과

Link

설명

1. 4개의 정수가 들어 있는 cards를 이용하여 ‘+’, ‘-‘, ‘*’, ‘/’ 연산자와 소괄호 ‘(‘, ‘)’ 문자를 이용하여 24를 만드는 문제이다.

2. cards를 실수 배열로 변환하여 3번에서 정의한 dfs(double[] cards) 메서드를 수행한 결과를 주어진 문제의 결과로 반환한다.

3. DFS 방식으로 cards를 이용하여 24를 만들 수 있는지 여부를 검증하기 위한 dfs(double[] cards) 메서드를 정의한다.
   • length에 cards의 길이를 저장한다.
   • length가 1인 경우, $cards[0] - 24$가 0이 아닌 작은 수인 0.001보다 작은지 여부를 반환한다.
   • 0부터 length 미만까지 i를 증가하고, $i + 1$부터 length 미만까지 j를 증가시키며 아래를 수행한다.
     • temp는 임시 검증 값을 담을 배열로, $length - 1$ 크기의 실수 배열로 초기화한다.
     • index를 0으로 정의하고, 0부터 length 미만까지 k를 증가시키며 k가 i나 j가 아닌 값일 경우, temp[index]에 cards[k]를 계속 넣어준다.
     • 4번에서 정의한 compute(double a, double b) 메서드의 수행 결과를 이용한 결과를 각각 d에 넣어 반복하여, temp의 마지막 위치에 d를 넣고 temp로 재귀 호출을 수행한 결과가 true인 경우 true를 반환한다.
   • 반복이 완료되면 24를 만들 수 없으므로, false를 반환한다.
4. a와 b를 이용하여 각 연산의 결과를 넣을 compute(double a, double b) 메서드를 정의한다.
   • a와 b를 ‘+’, ‘-‘, ‘*’, ‘/’ 연산자에 대입하여 나오는 모든 경우의 수를 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.