각 숫자가 1부터 9 범위 안에 있는 숫자 리스트가 고정된 순서로 주어져 있다고 가정해 보겠습니다. 숫자들 사이에 +(덧셈), -(뺄셈), *(곱셈), /(정수 나눗셈) 연산자를 배치하고, 필요하다면 괄호로 묶었을 때 결과값을 24로 만들 수 있는지 확인하는 것이 이번 문제의 목표입니다.
예를 들어 입력이 nums = [5, 3, 6, 8, 7]이라면 출력은 True입니다. (5 * 3) - 6 + (8 + 7) = 24가 성립하기 때문입니다.
해결 전략
이 문제는 분할 정복(divide and conquer) 기반의 재귀적 탐색으로 해결할 수 있습니다. 배열을 앞부분과 뒷부분으로 나누고, 각 부분에서 만들 수 있는 모든 값을 재귀적으로 계산한 뒤, 두 결과값을 사칙연산으로 조합하여 전체 식의 모든 경우의 수를 생성합니다.
구체적인 단계는 다음과 같습니다.
- recur() 함수 정의: 배열 arr을 인자로 받습니다.
- 결과를 저장할 빈 리스트 answer를 준비합니다.
- i를 0부터 (arr의 길이 - 2)까지 반복하며 다음을 수행합니다.
- pre := recur(arr[0 .. i]) — 앞부분에서 만들 수 있는 값들의 목록
- suf := recur(arr[i+1 .. 끝]) — 뒷부분에서 만들 수 있는 값들의 목록
- pre의 각 값 k와 suf의 각 값 j에 대해 다음을 answer에 추가합니다.
- k + j (덧셈)
- k - j (뺄셈)
- k * j (곱셈)
- j가 0이 아닌 경우 k // j (정수 나눗셈)
- answer가 비어 있고 arr의 길이가 1이라면 arr[0]을 answer에 추가합니다. (재귀의 기저 조건)
- answer를 반환합니다.
- 메인 메서드에서 recur(nums)의 결과 목록에 24가 존재하는지 확인하여, 존재하면 True, 그렇지 않으면 False를 반환합니다.
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
구현 예시
class Solution: def solve(self, nums): def recur(arr): answer = [] for i in range(len(arr) - 1): pre, suf = recur(arr[: i + 1]), recur(arr[i + 1 :]) for k in pre: for j in suf: answer.append(k + j) answer.append(k - j) answer.append(k * j) if j != 0: answer.append(k // j) if len(answer) == 0 and len(arr) == 1: answer.append(arr[0]) return answer return 24 in recur(nums) ob = Solution() nums = [5, 3, 6, 8, 7] print(ob.solve(nums))
입력
[5, 3, 6, 8, 7]
출력
True