679. 24 Game

문제

You are given an integer array cards of length 4. 
You have four cards, each containing a number in the range [1, 9]. 
You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] 
and the parentheses '(' and ')' to get the value 24.

You are restricted with the following rules:

The division operator '/' represents real division, not integer division.
For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Every operation done is between two numbers. In particular, we cannot use '-' as a unary operator.
For example, if cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed.
You cannot concatenate numbers together
For example, if cards = [1, 2, 1, 2], the expression "12 + 12" is not valid.
Return true if you can get such expression that evaluates to 24, and false otherwise.

• 4개의 정수로 이루어진 cards 배열이 주어진다.
• 이 정수들과 사칙연산 기호 및 괄호를 이용하여 24를 만들수 있는지 여부를 판별하라
  • 즉, 숫자의 순서는 상관이 없다.
• 나눗셈은 실수의 나눗셈을 사용한다.
• - 연산자는 절대 unary operator ( 한 수를 음수로 만드는 것 ) 으로 사용될수 없다.
  • Ex. 1 을 -1로 바꾸어 -1 - 1
• 숫자는 한자리만 주어지며, 이를 두자리 숫자로 붙힐수 없다.

---

예시

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

---

제한

• $cards.length == 4$
• $1 <= cards[i] <= 9$

---

풀이

• 약간 복잡한 백트래킹을 사용하는데, 먼저 코드를 본 후 조각내어 살펴보도록 하자
• 전반적인 원리는 다음과 같다
  • cards에서 랜덤하게 ( 물론 백트래킹이라 모든 경우를 다 보긴 하겠지만 ) 2개의 숫자를 꺼낸다.
  • 가능한 모든 연산을 적용해서 다시 넣는다
  • 만약 cards가 길이가 1이고 그 값이 24에 매우 가까울 경우 True 리턴한다.
    • 왜 24에 매우 가까울 경우로 하냐? 실수 연산이 있기 때문에 부동소수점 오차를 고려해야 한다.

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        EPS = 1e-6

        def backtracking() -> bool:
            N = len(cards)

            if N == 1 and abs(cards[0] - 24) < EPS:
                return True

            for i in range(N):
                for j in range(i + 1, N):
                    first = cards.pop(i)
                    second = cards.pop(j - 1)

                    results = [
                        first + second,
                        first * second,
                        first - second,
                        second - first
                    ]
                    if abs(second) > EPS:
                        results.append(first / second)
                    if abs(first) > EPS:
                        results.append(second / first)

                    for res in results:
                        cards.append(res)
                        if backtracking():
                            cards.pop()

                            cards.insert(j, second)
                            cards.insert(i, first)
                            return True
                        cards.pop()

                    cards.insert(j - 1, second)
                    cards.insert(i, first)

            return False

        return backtracking()

부분 해석

first = cards.pop(i)
second = cards.pop(j - 1)
...

cards.insert(j - 1, second)
cards.insert(i, first)

• 2개를 꺼냈다가 다시 넣는 부분

results = [
	first + second,
	first * second,
	first - second,
	second - first
]
if abs(second) > EPS:
	results.append(first / second)
if abs(first) > EPS:
	results.append(second / first)

• 연산을 모두 수행한다.

for res in results:
    cards.append(res)
    if backtracking():
        cards.pop()

        cards.insert(j, second)
        cards.insert(i, first)
        return True
    cards.pop()

• 수행한 연산들에 대해 백트래킹을 이어나간다, 만약 성공시 원복

---

---

리뷰

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        E = 1e-6

        def backtracking(arr: List[int]) -> bool:
            N = len(arr)

            if N == 1 and abs(arr[0] - 24) < E:
                return True

            for first in range(N):
                for second in range(first + 1, N):

                    f, s = arr[first], arr[second]

                    calc_result = []

                    calc_result.append(
                        f + s
                    )
                    calc_result.append(
                        f * s
                    )
                    calc_result.append(
                        f - s
                    )
                    calc_result.append(
                        s - f
                    )

                    if f != 0:
                        calc_result.append(s / f)
                    if s != 0:
                        calc_result.append(f / s)

                    new_arr = [v for i, v in enumerate(arr) if i != first and i != second]

                    for result in calc_result:
                        new_arr.append(result)
                        if backtracking(new_arr):
                            return True
                        new_arr.pop()

            return False

        return backtracking(cards)

• 백트래킹에 arr을 받도록 설정시, 복잡한 insert, pop 없이도 구현 가능하다.