leetcode hard : 24 Game

https://leetcode.com/problems/24-game/

24 Game - LeetCode

 

너무 어려워서 못풀었다. (는 사실 문제를 잘못 이해해서 혼자 어려운걸 하고 있었다.)

 

숫자를 어떻게든 arrange할 수 있고 사칙연산자랑 괄호를 어떻게 넣어도 상관없다. 주어진 숫자 4개와 사칙연산, 그리고 괄호를 가지고 24만 만들 수 있으면 된다. 근데 잘 생각해보자. 연산자랑 숫자를 어떻게 배치하든 결국 그 식을 계산하려면 어떤 두 숫자를 더하거나 빼거나 곱하거나 나눠야 된다. 그리고 사칙연산을 두 번 더 해야 단일 숫자 하나가 나온다. 어쨌든 어떤 두 수를 가지고 사칙연산 하는 작업을 3번을 해야 된다는 것이다. 그럼 두 수를 고르고 사칙연산 하는 작업을 3 번 하면 되지 않나? 해서 만들어진게 다음 솔루션이다.

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        
        def helper(numlst):
            if len(numlst) == 1 and abs(numlst[0] - 24) < 0.0001:
                return True
            
            for i in range(len(numlst)-1):
                for j in range(i+1, len(numlst)):
                    remaining = [numlst[x] for x in range(len(numlst)) if x != i and x != j]
                    
                    if helper(remaining + [ numlst[i] + numlst[j] ]): return True
                    if helper(remaining + [ numlst[i] - numlst[j] ]): return True
                    if helper(remaining + [ numlst[j] + numlst[i] ]): return True
                    if helper(remaining + [ numlst[j] - numlst[i] ]): return True
                    if helper(remaining + [ numlst[i] * numlst[j] ]): return True
                    if numlst[i] and helper(remaining + [numlst[j]/numlst[i]]): return True
                    if numlst[j] and helper(remaining + [numlst[i]/numlst[j]]): return True
                    
            return False
        
        return helper(cards)

정말 우아하다.

<0.0001 이거는 문제 조건때문에 넣은거다. 나눗셈이 정수 나눗셈이 아니라서 3.99999997 이런식으로 답이 나오는 경우에 정답임을 식별하기 위해 넣는 조건.

 

이 문제는 다르게 생각해보면 4개의 숫자의 permutation을 구해서 그 사이에 사칙연산자를 끼워넣고 계산해서 정답을 구할 수도 있다. (다만 이러면 중복이 좀 생기긴한다. 1 * 2 + 3 + 4와 2 * 1 + 3 + 4)

def judgePoint24(self, nums):
    if len(nums) == 1: return math.isclose(nums[0], 24)
    return any(self.judgePoint24([x] + rest) for a, b, *rest in itertools.permutations(nums) for x in {a+b, a-b, a*b, b and a/b})

ㅋㅋㅋㅋㅋㅋ 리트코드 하드를 2줄로 푸는 미친인간들이 있는 곳이 바로 leetcode discussion. 정말 대단하다..

진짜 뭐 말이 안되네 그냥 ㅋㅋㅋ