[LeetCode] 679. 24 Game

문제 출처: https://leetcode.com/problems/24-game/

24 Game - LeetCode

 

문제

길이 4인 정수 배열 cards가 주어지며, 4장의 카드는 각각 [1, 9]범위의 숫자를 갖고 있다. 4장의 카드를 사칙연산(['+', '-', '*', '/'])과 괄호 쌍 ('(', ')')을 이용하여 그 결과가 24가 되도록 재배열하려고 한다.

 

다음의 제약이 존재한다:

• 나누기 연산자인 '/'은 정수 나누기가 아닌 실수 나누기이다.
  • 예를 들어, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
• 모든 연산의 수행은 두 숫자 사이에서 수행된다. 즉, '-'를 단항 연산자로 사용할 수 없다.
  • 예를 들어, 만약 cards = [1, 1, 1, 1](이)라면, "-1 -1 -1 -1"은 불가능한 표현입니다.
• 숫자를 합칠 수 없습니다.
  • 예를 들어, 만약 cards = [1, 2, 1, 2](이)라면, "12 +12"는 유요하지 않은 수식입니다.

 

만약 수식의 결과로 24를 얻을 수 있다면 true를 반환하고 그렇지 않다면 false를 반환하라.

 

예제

Input: cards = [4,1,8,7]
Output: true

Explanation: (8-4) * (7-1) = 24

Input: cards = [1,2,1,2]
Output: false

 

풀이

입력으로 주어지는 4개의 숫자로 만들 수 있는 모든 수식을 만들어 확인하는 방법으로 문제를 해결할 수 있다.

 

사칙연산에서 연산자가 고정되어 있다고 가정할 때, 결과에 영향을 주는 요인은 괄호의 위치와 숫자의 위치이다.

1. 괄호의 위치 : 1 + (2 * 3) != (1 + 2) * 3
2. 숫자의 위치 : 1 + (2 * 3) != 2 + (1 * 3)

숫자의 위치의 경우 4개의 숫자로 만들 수 있는 모든 순열을 구하는 것으로

function getPerms(remain) {
    if (remain.length == 0) {
        return [[]];
    }

    let ans = [];

    for (let i = 0; i < remain.length; i++) {
        const before = remain.slice(0, i);
        const after = remain.slice(i+1);

        const perms = getPerms([...before, ...after]);
        for (let perm of perms) {
            ans.push([remain[i], ...perm]);
        }
    }

    return ans;
}

다음으로 괄호에 대해서 생각해보자.

 

사칙연산에서 괄호는 연산자 우선순위가 낮더라도 먼저 계산을 수행하라는 의미이다. 이에 대해서 임의로 한 위치를 선택, 선택한 위치를 기준으로 왼쪽과 오른쪽으로 나눠서 해당 부분에 대한 계산을 먼저 수행하는 방식으로 연산자 우선순위와 별개로 연산이 수행되도록 할 수 있다.

예를 들어, a op b op c 이라는 수식이 있을 때, 아래와 같이 2가지 케이스를 만들 수 있다.
(a, b, c: 숫자, op: 연산자 '+' or '-' or '*' or '/')

a op b op c
↑          => (a) op (b op c)
    ↑      => (a op b) op (c)


이를 4개의 숫자로 확장한다면, 아래와 같다.
(a, b, c: 숫자, op: 연산자 '+' or '-' or '*' or '/')

a op b op c op d
↑                => (a) op (b op c op d)
                    => (a) op ((b) op (c op d))
                    => (a) op ((b op c) op (d))
     ↑           => (a op b) op (c op d)
          ↑      => (a op b op c) op (d)
                    => ((a) op (b op c)) op (d)
                    => ((a op b) op (c)) op (d)

이러한 방식으로 만들 수 있는 사칙연산의 케이스를 모두 계산하는 함수를 작성하면 다음과 같다.

function calcAllCase(nums, left, right) {
    if (left == right) {
        return [nums[left]];
    }

    const ops = (a, b) => [a+b, a-b, a*b, b ? a/b : Infinity];
    const ans = [];

    // 괄호의 위치를 지정하는 반복문
    for (let i = left; i < right; i++) {
        // 연산자를 기준으로 왼쪽과 오른쪽 분리
        const lefts = calcAllCase(nums, left, i);
        const rights = calcAllCase(nums, i+1, right);

        // 왼쪽 값과 오른쪽 값에 대해서 사칙연산을 수행하여 결과에 추가
        for (let l of lefts) {
            for (let r of rights) {
                ans.push(...ops(l, r));
            }
        }
    }

    return ans;
}

최종적으로 위 두 함수를 이용하여 다음의 코드로 문제에 대한 답을 찾을 수 있다.

function judgePoint24(cards) {
    const perms = getPerms(cards);

    for (let perm of perms) {
        const results = calcAllCase(perm, 0, 3);
        for (let result of results) {
            if (Math.abs(24 - result) < 10e-14) { return true; }
        }
    }

    return false;
}

Github: 679.js

opwe37/Algorithm-Study