★Partition Array(0/100)★

Partition Array Into Two Arrays to Minimize Sum Difference - LeetCode

★다시 풀어봐야할 문제★ (결국 못풀었음, 다음 다시 풀때 meet in the middle 알고리즘 반복 이해 해보기)

접근 방법 [필수 작성]

제한 조건 확인

Constraints:

• 1 <= n <= 15
• nums.length == 2 * n
• 107 <= nums[i] <= 107

num 배열의 길이가 최대 2*n → 30 밖에 안된다.

굉장히 길이가 짧으므로 완전탐색을 고려해볼 수 있다.

아이디어

문제에서는 파티션이라는 단어를 썼는데, 그냥 쉽게 생각하면 nums 라는 메인통에서 숫자를 배열1이나 배열2로 나누는 작업이다. 그래서 특정 원소가 배열1로 갈지 배열2로 갈지만 정해주면 된다.

절대값 차이가 줄어드는 방향으로만 재귀적 탐색을 실행함

절대값 차이 계산법은 각 리스트에 분배 후 더한 후 차이를 구할 수도 있지만,

어차피 배열1 숫자들은 전체에서 배열2 숫자들을 배제한 것과 다름이 없으니,

배열1 합 + 배열2 합 = 전체 합

abs(배열1합 - 배열2합) = abs(배열1합 - (전체 합 - 배열1 합)) = abs(배열1 합*2 - 전체합)

여기서 전체합은 상수이고, 배열1 합만 동적으로 변하게 된다.

만약 위의 값이 늘어나면 탐색을 중단하고 다음 재귀루프로 들어가는식으로 구현하면

완전탐색의 불필요한 부분을 상당 수 제거하고 시간제한을 통과할 수 있을것으로 예상된다.

시간복잡도

최대 30개의 원소에 대해서 특정원소가 배열1에 포함될지 말지의 경우의 수 → 2^30 → 102410241024 → ~ 10^(3*3) → 10^9 이므로 시간초과 → 그냥 박치기 하면 안되고, 뭔가 문제특성을 이해해서 시간복잡도를 줄일 수 있는 방법을 생각해야함 → 절대값 차이가 줄어드는 방향으로만 탐색을 한다면?

자료구조

코드 구현 [필수 작성]

첫번째시도

재귀 구현 파트에서 꼬여서 포기함

종료조건 및 껍질파고들어가는 조건 작성하다가 복잡해서 포기하고 다음문제 넘어감

# 6시10분 시작 -> 7시 중간점검

import sys

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        sum_nums = 0
        res = sys.maxsize

        for num in nums:
            sum_nums += num
        
        def find_minimum_diff(sum_array_1, min_diff,start): #backtracking
            nonlocal sum_nums
            nonlocal res

            curr_diff = abs(sum_array_1*2 - sum_nums)

            if start == len(nums):
                return True

            for i in range(start,len(nums)):
                sum_array_1 += nums[i]
                curr_diff = abs(sum_array_1*2 - sum_nums)
                if curr_diff <= min_diff:
                    res = min_diff
                    if find_minimum_diff(sum_array_1, min_diff, i+1):
                        return True
                sum_array_1 -= nums[i]
            return False
        
        return res

두번째 시도

재귀 구현을 print 디버깅을 통해 해결하고 test_case 를 모두 통과하는 상대로 만들었으나

실제 test_case 에서 실패함

print 를 통해 내가 의도한대로 재귀가 돌지 않는 것을 발견하고 코드를 다시 세번째 시도처럼 수정함

# 6시10분 시작 -> 7시 중간점검

import sys

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        sum_nums = 0
        min_diff = 9999999999
        count = 0

        for num in nums:
            sum_nums += num
        
        def find_minimum_diff(sum_array_1, start): #backtracking
            nonlocal sum_nums
            nonlocal min_diff
            nonlocal count

            print("======================")
            print("function_call")
            print("현재 min_diff는 "+str(min_diff)+"이다")
            curr_diff = abs(sum_array_1*2 - sum_nums)
            print("curr_diff=", curr_diff)

            if curr_diff <= min_diff and count == len(nums)//2:
                    print("정확히 절반이고, 더 작은 diff 를 찾았다!")
                    min_diff = curr_diff
                    return
            else:
                if curr_diff > min_diff or count >= len(nums)//2:
                    print("이건 더 큰 diff를 만들거나 이미 절반이상 원소갯수가 들어왔다. 껍질까고 나오기.")
                    return

            for i in range(start,len(nums)):
                print("현재 "+str(i)+"번째 원소를 탐색중...")
                sum_array_1 += nums[i]
                count += 1
                print(str(nums[i])+"를 추가해서 현재 array1의 합은 "+str(sum_array_1)+" 이고, 갯수는 "+str(count)+"개 이다.")
                find_minimum_diff(sum_array_1, i+1)
                sum_array_1 -= nums[i]
                count -= 1
                print("")
                print(str(nums[i])+"를 제거하고 현재 array1의 합은 "+str(sum_array_1)+" 이고, 갯수는 "+str(count)+"개 이다.")
            print("끝까지 다 돌았다... fucntion 종료...")
            
        find_minimum_diff(0,0)
        
        return min_diff

세번째 시도

의도한 대로 코드가 돌지만 시간 초과 발생

내 아이디어를 유지하되 이진탐색을 통해 코드를 좀 더 효율적으로 바꿀 수는 없는지 고민 시작

아래 raw_data 를 보면 재귀를 돌면서

3,9,7,3 에 대해서

3,9

3,7

9,3

7,3

과 같이 위 네 가지 경우가 사실은 동일한 경우인데 중복해서 도는 비효율이 발생한다.

어떻게 개선할 수 있을까?

3,9,7,4 의 경우는

3,9 한가지 케이스만 나온다.

즉, 이런 비효율이 발생하는 이유는 nums 리스트내 동일한 원소가 있을 때 발생한다고 볼 수 있다.

그렇다면, 동일한 원소가 짝수개씩 있을때는 양쪽으로 각각 나누어 줘도 괜찮을까? → 땡

반례 → 4,4,13,1

그럼 결국 이진탐색을 활용해야하는데, 일단 원소를 정렬해보면,

3,3,7,9

→ 이 이상으로 내 아이디어를 발전시킬 수 없어서 그냥 해설코드리뷰로 넘어가기로 함.

# 6시10분 시작 -> 7시 중간점검

import sys

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        sum_nums = 0
        min_diff = 9999999999
        count = 0

        for num in nums:
            sum_nums += num
        
        def find_minimum_diff(sum_array_1, start): #backtracking
            nonlocal sum_nums
            nonlocal min_diff
            nonlocal count

            #print("======================")
            #print("function_call")
            #print("현재 min_diff는 "+str(min_diff)+"이다")
            curr_diff = abs(sum_array_1*2 - sum_nums)
            #print("curr_diff=", curr_diff)
            
            if count == len(nums)//2:
                if curr_diff < min_diff:
                    #print("정확히 절반이고, 더 작은 diff 를 찾았다!")
                    min_diff = curr_diff
                    return
                else:
                    #print("절반은 맞지만, 더 작은 diff 가 아니다")
                    return

            for i in range(start,len(nums)):
                #print("현재 "+str(i)+"번째 원소를 탐색중...")
                sum_array_1 += nums[i]
                count += 1
                #print(str(nums[i])+"를 추가해서 현재 array1의 합은 "+str(sum_array_1)+" 이고, 갯수는 "+str(count)+"개 이다.")
                find_minimum_diff(sum_array_1, i+1)
                sum_array_1 -= nums[i]
                count -= 1
                #print("")
                #print(str(nums[i])+"를 제거하고 현재 array1의 합은 "+str(sum_array_1)+" 이고, 갯수는 "+str(count)+"개 이다.")
            #print("끝까지 다 돌았다... fucntion 종료...")
            
        find_minimum_diff(0,0)
        
        return min_diff

#raw_data
======================
function_call
현재 min_diff는 9999999999이다
curr_diff= 22
현재 0번째 원소를 탐색중...
3를 추가해서 현재 array1의 합은 3 이고, 갯수는 1개 이다.
======================
function_call
현재 min_diff는 9999999999이다
curr_diff= 16
현재 1번째 원소를 탐색중...
9를 추가해서 현재 array1의 합은 12 이고, 갯수는 2개 이다.
======================
function_call
현재 min_diff는 9999999999이다
curr_diff= 2
정확히 절반이고, 더 작은 diff 를 찾았다!

9를 제거하고 현재 array1의 합은 3 이고, 갯수는 1개 이다.
현재 2번째 원소를 탐색중...
7를 추가해서 현재 array1의 합은 10 이고, 갯수는 2개 이다.
======================
function_call
현재 min_diff는 2이다
curr_diff= 2
절반은 맞지만, 더 작은 diff 가 아니다

7를 제거하고 현재 array1의 합은 3 이고, 갯수는 1개 이다.
현재 3번째 원소를 탐색중...
3를 추가해서 현재 array1의 합은 6 이고, 갯수는 2개 이다.
======================
function_call
현재 min_diff는 2이다
curr_diff= 10
절반은 맞지만, 더 작은 diff 가 아니다

3를 제거하고 현재 array1의 합은 3 이고, 갯수는 1개 이다.
끝까지 다 돌았다... fucntion 종료...

3를 제거하고 현재 array1의 합은 0 이고, 갯수는 0개 이다.
현재 1번째 원소를 탐색중...
9를 추가해서 현재 array1의 합은 9 이고, 갯수는 1개 이다.
======================
function_call
현재 min_diff는 2이다
curr_diff= 4
현재 2번째 원소를 탐색중...
7를 추가해서 현재 array1의 합은 16 이고, 갯수는 2개 이다.
======================
function_call
현재 min_diff는 2이다
curr_diff= 10
절반은 맞지만, 더 작은 diff 가 아니다

7를 제거하고 현재 array1의 합은 9 이고, 갯수는 1개 이다.
현재 3번째 원소를 탐색중...
3를 추가해서 현재 array1의 합은 12 이고, 갯수는 2개 이다.
======================
function_call
현재 min_diff는 2이다
curr_diff= 2
절반은 맞지만, 더 작은 diff 가 아니다

3를 제거하고 현재 array1의 합은 9 이고, 갯수는 1개 이다.
끝까지 다 돌았다... fucntion 종료...

9를 제거하고 현재 array1의 합은 0 이고, 갯수는 0개 이다.
현재 2번째 원소를 탐색중...
7를 추가해서 현재 array1의 합은 7 이고, 갯수는 1개 이다.
======================
function_call
현재 min_diff는 2이다
curr_diff= 8
현재 3번째 원소를 탐색중...
3를 추가해서 현재 array1의 합은 10 이고, 갯수는 2개 이다.
======================
function_call
현재 min_diff는 2이다
curr_diff= 2
절반은 맞지만, 더 작은 diff 가 아니다

3를 제거하고 현재 array1의 합은 7 이고, 갯수는 1개 이다.
끝까지 다 돌았다... fucntion 종료...

7를 제거하고 현재 array1의 합은 0 이고, 갯수는 0개 이다.
현재 3번째 원소를 탐색중...
3를 추가해서 현재 array1의 합은 3 이고, 갯수는 1개 이다.
======================
function_call
현재 min_diff는 2이다
curr_diff= 16
끝까지 다 돌았다... fucntion 종료...

3를 제거하고 현재 array1의 합은 0 이고, 갯수는 0개 이다.
끝까지 다 돌았다... fucntion 종료...

해설코드

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        ans = inf
        goal = sum(nums) / 2

        def add_subset(lst):
            result = [[] for _ in range(0, len(lst)+1)]
            for i in range(0, len(lst)+1):
                for comb in combinations(lst, i):
                    result[i].append(sum(comb))
            return result
        
        lefts = add_subset(nums[:len(nums)//2])
        rights = add_subset(nums[len(nums)//2:])
        for i, left in enumerate(lefts):
            right = sorted(rights[len(rights)-1-i])
            for j in left:
                k = bisect_left(right, goal-j)
                if k < len(right):
                    ans = min(ans, right[k] + j - goal)
        return int(ans*2)

배우게 된 점 [ 필수 X ]

영문 description 문제라 대충 읽었다가, 문제조건 놓쳤음. 배열1과 2는 정확히 N개로 총 원소갯수의 절반씩 갖고 있음.

이진탐색으로 푸는 방법 → 정석적인 방법

내 아이디어에서 추가적인 아이디어 발전을 통해 재귀로 푸는 방법이 과연 가능할까? → 더이상 아이디어를 발전시킬만한 방법이 떠오르지 않아서 포기 → 해설코드리뷰로 넘어감

질문 [ 필수 X ]

Q1

재귀 구현할때, 껍질 까고 나오는거(종료조건?) 구현을 직관적으로 이해하거나 떠올리기가 쉽지가 않음.

항상 이부분에서 막힘. 재귀가 어떻게 돌아가고 있는건지 잘 이해가 안됨. → print 를 활용한 디버깅 애용하기!

Q2 (추가질문)

1시간 정도 고민 후 아이디어 발전을 포기하고 해설코드를 보았는데, print 문을 찍어보아도 해설코드의 아이디어가 직관적으로 잘 이해가 안됩니다. 관련 해설글을 찾아보아도 서치가 어렵습니다. 해설이 있다면 링크를 걸어주시면 감사드리고, 없다면 아이디어를 간단히 설명해주시면 감사드리겠습니다.

Q3 (추가질문)

내 아이디어에서 추가적인 아이디어 발전을 통해 재귀로 푸는 방법이 과연 가능할까? → 더이상 아이디어를 발전시킬만한 방법이 떠오르지 않아서 포기 → 해설코드리뷰로 넘어감 발전 아이디어가 있다면 조언을 구해보고 싶고, 없다면, 왜 아이디어를 폐기해야만 하는지 알고 싶습니다.

피드백 [ 코치 작성 ]

화이팅입니다!

print를 통한 디버깅 외에도 직접 의사결정트리를 그려 흐름을 파악하는 것, function call이 스택에 쌓이는 모습 등을 이해하시는 것 또한 도움이 될 것입니다.

A2

해당 알고리즘은 meet in the middle이라 불리는 알고리즘으로 O(2^n)의 시간이 걸리는 알고리즘을O(2*2^(n/2))로 줄여주는 알고리즘입니다. 해당 알고리즘이 이 문제에 적용된 방식은 배열을 둘로 나누어 각각의 배열에서 원소를 뽑아 부분 집합을 만드는 목적으로 사용되었습니다. 즉 nums[:len(nums)//2]와 nums[len(nums)//2:]로 분리된 배열에서 각각 원소를 뽑고 총 len(nums)/2개의 원소를 뽑아 부분 집합을 만드는 것입니다. 왼쪽 배열에서 i개의 원소를 뽑았다면 오른쪽 배열에서는 len(nums)/2-i개의 원소를 뽑아야 하기에 lefts와 rights를 생성할 때 조합 시 뽑을 원소의 개수별로 분리를 한 것이며 이를 통해 lefts에서 선택한 원소의 개수와 rights에서 선택한 원소의 개수를 맞추어 이진 탐색을 진행합니다. 이 때 생성해야할 부분 집합의 합의 가장 이상적인 값은 nums 전체 합의 절반인 goal이므로 goal-j를 통해 이진 탐색을 진행한 것 입니다.

A3

해당 코드에서 최적화 할 점은 크게 보이지 않습니다. 한가지 최적화 할만한 사항은 [a, b, c, d]의 경우 array1을 [a, b]로 선정하는 경우 [c, d]는 array2에서 사용한 것과 같으며 이는 array1이 [c, d], array2가 [a, b]로 선정된 것과 동일한 결과입니다. 즉 현재 동일한 경우를 2번 수행하고 있으며 이는 한 원소가 항상 array1에 들어가는 것으로 고정함을 통해 해결할 수 있습니다.

count = 1 #시작시 1가지 요소 존재
find_minimum_diff(nums[0], 1) #시작시 nums[0]을 array1에 들어간다고 가정, start는 1에서 시작

이는 실행 시간을 절반만큼 줄일 수 있지만 근본적인 해결 방법이 되지 못합니다.

계산해본 결과 원인은 다음과 같습니다.

재귀를 수행하는 과정 중 의사결정트리를 그리면 root node 1개부터 leaf node 30C15개까지 생성됩니다.(1개의 요소를 고정하는 것을 고려하면 29C14입니다.) 즉 호출되는 재귀 함수의 총 개수는 30C0 + 30C1 + 30C2 + … 30C15이며 이는 10^8 이상의 범위를 갖고 재귀적으로 구현된 특성 상 오버헤드가 자주 발생하기에 실행 시간이 크게 증가하게 됩니다. 그렇기에 해당 아이디어를 최적화 해도 파이썬으로는 제출 시 합격이 힘들 것 같습니다.(leetcode는 언어별 통과 시간이 동일하기에 C와 같은 low level언어로 작성하면 통과할 가능성이 있을 것으로 보입니다.)