Home [Leetcode] Partition Equal Subset Sum - memoization 적용
Post
Cancel

[Leetcode] Partition Equal Subset Sum - memoization 적용

FANG에서 출제된 문제는 보기보다 간단한 경우가 많은것 같다. 처음에는 backtracking으로 접근을 하긴 했지만 시간복잡도가 O($2^N$)이기 때문에 접근을 포기했다. DP로 풀자니 어떤 부분을 subproblem으로 나눠야 하는지 잘 보이지 않았고, 더 오래 고민했으면 풀수도 있었을것 같다.

다음은 Top down DP로 풀이한 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums){
            total += num;
        }
        if (total % 2 != 0){
            return false;
        }

        return canPartition(nums,total,0,0,new HashMap<>());
    }

    public boolean canPartition(int[] nums, int total, int index, int sum, Map<String,Boolean> map) {
        String key = String.format("%d|%d",index,sum);
        if (index >= nums.length || sum > total/2) {
            return false;
        }
        if (map.containsKey(key)){
            return map.get(key);
        }
        if (sum * 2 == total) { 
            return true;
        }
        boolean result = canPartition(nums,total,index+1,sum+nums[index],map) || canPartition(nums,total,index+1,sum,map);
        map.put(key,result);
        return result;
    }
}

위 부분에서 놓치기 쉬운 부분은 이 부분인것 같다.

1
2
3
if (index >= nums.length || sum > total/2) {
        return false;
    }

sum가 total/2 보다 클때 함수를 리턴하지 않으면 결국은 TLE 가 나기 때문이다.

위의 시간복잡도는 O(N * M), N : 인풋크기 M : 원소의 총합 / 2

This post is licensed under CC BY 4.0 by the author.

[BOJ 1038-감소하는수] 집합이론을 이용한 추론

Apache Kafka 장단점

Comments powered by Disqus.

Trending Tags