[Grind75-LeetCode] Partition Equal Subset Sum JAVA

알고리즘/코딩테스트-Grind75

[Grind75-LeetCode] Partition Equal Subset Sum JAVA

kwang2134 2024. 11. 11. 15:32

728x90

[Grind75-LeetCode] Partition Equal Subset Sum - Medium

접근

풀이

주어진 정수 배열 내의 값을 동등한 부분 합으로 만들 수 있는지 검사하는 문제이다. 예제 1번처럼

nums = [1,5,11,5] -> [1, 5, 5] and [11]

동일한 부분합으로 분리할 수 있는지 확인하는 것이다. 예제 1번이 [1, 5, 5]와 [11]로 분리되어 원소들을 더 한 값이 배열에 존재하는가와 같은 문제 이해를 잘못할 수 있는데

nums = [3,3,3,4,5] -> [3,3,3] and [4,5]

위처럼 단순히 부분합이 같은 두 집합으로 분리하는 것이다.

    public boolean canPartition(int[] nums) {
        int target = 0;

        for (int num : nums) {
            target += num;
        }

        if (target % 2 == 1) {
            return false;
        }

        target /= 2;

우선 부분합이 같은 두 배열로 분리하려면 배열 내 모든 값을 더 했을 때 기본적으로 짝수여야 한다. 같은 값을 가지기 위해선 전체 합의 2로 나눈 값으로 양쪽 배열의 합이 맞춰져야 하는데 홀수인 경우 애초에 불가능하기에 바로 false를 반환해 주면 된다. 그리고 합이 짝수라면 절반을 나눈 값이 우리가 맞춰야 하는 목푯값이 된다.

	boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }

        return dp[target];
    }

dp를 사용한 방법이다. dp 배열을 target의 크기만큼 생성하고 0번 인덱스는 언제나 true이다. dp배열은 해당 부분합을 만들 수 있는지 검사해 만들 수 있다면 해당 인덱스가 true가 되는데 부분합 0은 무조건 만들 수 있기 때문에 true가 된다. 숫자 배열을 순회하며 dp 배열을 채운다. target의 값부터 거꾸로 채워가기 시작하는데 뒤에서부터 갱신을 시작해야 각 숫자를 한 번만 사용할 수 있기 때문이다. 앞에서부터 순차적으로 갱신하는 경우와 뒤에서부터 역순으로 갱신하는 것의 차이를 보면 알 수 있다.

앞에서 부터 갱신하는 경우 target = 5, num = 1
dp[1] = dp[1] || dp[i-1] = dp[1] || dp[0] = true
dp[2] = dp[2] || dp[i-1] = dp[2] || dp[1] = true
.
.
dp[5] = dp[5] || dp[4] = true -> 앞의 결과가 중복으로 사용되어 해당 숫자가 한 번만 사용됨을 보장할 수 없음

뒤에서 부터 갱신하는 경우 target = 5, num = 1
dp[5] = dp[5] || dp[4] = false
dp[4] = dp[4] || dp[3] = false
.
.
dp[1] = dp[1] || dp[0] = true -> 한 개의 숫자당 한 번의 사용이 보장 가능

앞에서부터 갱신을 할 경우 해당 숫자를 한 번만 사용한다는 보장이 불가능하다. 1을 사용해 부분합 2를 만든다고 가정할 때 역순으로 진행할 경우 부분합 2를 만들기 위해선 부분합 1이 true로 만들 수 있는 상태여야 가능하다. 역순으로 갱신을 할 경우 부분합 1을 만드는 것보다 2를 만드는 검사를 우선으로 만나기 때문에 1이 false인 상태라면 부분합 2는 만들지 못하는 것으로 체크하고 넘어가게 된다. 그러나 앞에서부터 갱신을 진행하게 되면 부분합 1을 만드는 검사를 먼저 만나게 되고 1 한 개를 사용해 부분합 1을 만들 수 있다고 체크하고 부분합 2 검사를 수행하게 된다. 그렇게 부분합 2 검사를 넘어가게 되었을 때 숫자 한 번 사용을 보장하기 위해선 다시 true가 된 dp [1]을 false인 상태로 검사를 해야 하는데 이미 true가 된 상태에서 검사가 진행되기 때문에 dp [2]로 true로 체크되어 버리지만 사실상 dp [2]를 만들기 위해 숫자 1을 두 번 사용해 버리는 게 되는 것이다. 그렇게 dp 배열이 만들어지면 target을 체크해 부분합 생성이 가능한지 반환하면 된다. 배열 내 절반 값이 되는 부분집합이 존재한다면 나머지 값의 합도 동일하기 때문에 true가 되는 것이다.

dfs + 메모이제이션

위의 dp가 bottom-up 방식으로 풀어졌다면 top-down 방식의 dfs와 메모이제이션을 사용해 풀어진 코드를 들고 왔다. 역시나 dfs를 사용해 모든 경우의 수를 탐색해도 풀 수 있는 문제이다.

    public boolean canPartition(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 != 0) return false;
        
        int subSetSum = total / 2;
        int n = nums.length;
        Boolean[][] memo = new Boolean[n + 1][subSetSum + 1];
        return dfs(nums, n - 1, subSetSum, memo);
    }

총합과 목푯값을 구하는 과정은 동일하고 메모이제이션 배열을 사용해 최적화가 진행되었다.

    private boolean dfs(int[] nums, int n, int subSetSum, Boolean[][] memo) {
        if (subSetSum == 0) return true;
        
        if (n == 0 || subSetSum < 0) return false;
        
        if (memo[n][subSetSum] != null) return memo[n][subSetSum];
        
        Boolean result = dfs(nums, n - 1, subSetSum - nums[n - 1], memo) || dfs(nums, n - 1, subSetSum, memo);
        
        memo[n][subSetSum] = result;
        return result;
    }

dfs 코드이다. 목푯값인 subSetSum에서 값을 빼며 진행하기 때문에 0이 되면 만들 수 있는 경우로 true를 반환하게 된다. 그리고 n이 0이 되거나 목푯값이 음수가 된다면 이미 끝까지 탐색했거나 잘못된 경로이므로 false를 반환해 해당 경로를 종료시켜 준다. 그리고 이미 메모이제이션 배열에 이미 계산된 결과가 존재한다면 그 값을 그대로 반환하여 연산을 줄여준다. 다음 단계로 넘어가는 재귀 호출은 현재 수를 더한 경우와 더하지 않은 경우로 갈라진다. 현재 수를 더해야 될 수도 더하지 않아야 될 수도 있기 때문에 두 경우가 나눠져 진행된다. 그리고 해당 결과를 배열에 저장하는데 이 방법 또한 dp와 마찬가지로 숫자의 중복 사용을 막기 위해 역순으로 접근하게 된다.

dp보다 좋은 성능을 나타냈다.

0ms

제일 빠른 시간에 수행된 코드는 어떤 코드인지 살펴봤는데 정말 예상치 못한 코드가 나왔다. 우선 코드부터 보고 말을 해야 할 것 같다.

    public boolean canPartition(int[] nums) {     
        int sum = 0;
        int n = nums.length;
        if(n>1 && nums[n-1]==100 && nums[0]==97) return false;
        if(n==1){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==5 && nums[n-2]==2){
            return false;
        }
        if(nums[0]==2 && nums[n-1]==5 && nums[n-2]==3){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==3 && nums[n-2]==11){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==4 && nums[n-2]==4){
            return false;
        }
        if(nums[0]==2 && nums[n-1]==12 && nums[n-2]==9){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==5 && nums[n-2]==5 &&nums[1]==3){
            return false;
        }
        if(nums[0]==2 && nums[n-1]==1 && nums[n-2]==13){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==1 && nums[n-2]==35){
            return false;
        }
        if(nums[0]==9 && nums[n-1]==5){
            return false;
        }
        if(nums[0]==99 && nums[n-1]==1){
            return false;
        }
        if(nums[0]==100 && nums[n-1]==97 && nums[n-2]==99){
            return false;
        }
        if(nums[0]==4 && nums[n-1]==99 && nums[n-2]==97){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==100 && nums[n-2]==1){
            return false;
        }
        if(nums[0]==18 && nums[n-1]==1 && nums[n-2]==1){
            return false;
        }
        if(nums[0]==7 && nums[n-1]==9 && nums[n-2]==31){
            return false;
        }
        if(nums[0]==33 && nums[n-1]==23 && nums[n-2]==46){
            return false;
        }
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        int c = 0;
        if(sum%2!=0){
            return false;
        }else{
            for(int i=0;i<n;i++){
                if(nums[i]==(sum/2)){
                    return true;
                }else{
                    c++;
                }
            }
        }
        return true;
    }

역시 가장 원시적인 방식이 제일 빠르다고 자세히는 모르겠지만 만들 수 없는 불가능한 경우를 모두 하드코딩해 걸러낸 코드인 것 같다. 현재 변수 c는 사용이 안되고 있어 사실상 위의 조건문을 전부 통과하고 총합이 짝수라면 통과되고 있는 코드이다.

	for(int i=0;i<n;i++){
            sum+=nums[i];
        }

        if(sum%2!=0){
            return false;
        }

        return true;

사실상 마지막 조건문 아래는 이것과 같고 수학적인 방법이라 해야 하나 아무튼 대단한 거 같긴 하다.

전체 코드

class Solution {
    public boolean canPartition(int[] nums) {
        int target = 0;

        for (int num : nums) {
            target += num;
        }

        if (target % 2 == 1) {
            return false;
        }

        target /= 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }

        return dp[target];
    }
}

dfs + 메모이제이션

class Solution {
    public boolean canPartition(int[] nums) {
        int total = Arrays.stream(nums).sum();
        if (total % 2 != 0) return false;
        
        int subSetSum = total / 2;
        int n = nums.length;
        Boolean[][] memo = new Boolean[n + 1][subSetSum + 1];
        return dfs(nums, n - 1, subSetSum, memo);
    }

    private boolean dfs(int[] nums, int n, int subSetSum, Boolean[][] memo) {
        if (subSetSum == 0) return true;
        if (n == 0 || subSetSum < 0) return false;
        if (memo[n][subSetSum] != null) return memo[n][subSetSum];
        Boolean result = dfs(nums, n - 1, subSetSum - nums[n - 1], memo)
        || dfs(nums, n - 1, subSetSum, memo);
        memo[n][subSetSum] = result;
        return result;
    }
}

하드코딩

class Solution {
 public boolean canPartition(int[] nums) {     
        int sum = 0;
        int n = nums.length;
        if(n>1 && nums[n-1]==100 && nums[0]==97) return false;
        if(n==1){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==5 && nums[n-2]==2){
            return false;
        }
        if(nums[0]==2 && nums[n-1]==5 && nums[n-2]==3){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==3 && nums[n-2]==11){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==4 && nums[n-2]==4){
            return false;
        }
        if(nums[0]==2 && nums[n-1]==12 && nums[n-2]==9){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==5 && nums[n-2]==5 &&nums[1]==3){
            return false;
        }
        if(nums[0]==2 && nums[n-1]==1 && nums[n-2]==13){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==1 && nums[n-2]==35){
            return false;
        }
        if(nums[0]==9 && nums[n-1]==5){
            return false;
        }
        if(nums[0]==99 && nums[n-1]==1){
            return false;
        }
        if(nums[0]==100 && nums[n-1]==97 && nums[n-2]==99){
            return false;
        }
        if(nums[0]==4 && nums[n-1]==99 && nums[n-2]==97){
            return false;
        }
        if(nums[0]==1 && nums[n-1]==100 && nums[n-2]==1){
            return false;
        }
        if(nums[0]==18 && nums[n-1]==1 && nums[n-2]==1){
            return false;
        }
        if(nums[0]==7 && nums[n-1]==9 && nums[n-2]==31){
            return false;
        }
        if(nums[0]==33 && nums[n-1]==23 && nums[n-2]==46){
            return false;
        }
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        int c = 0;
        if(sum%2!=0){
            return false;
        }else{
            for(int i=0;i<n;i++){
                if(nums[i]==(sum/2)){
                    return true;
                }else{
                    c++;
                }
            }
        }
        return true;
    }
}

728x90

'알고리즘 > 코딩테스트-Grind75' 카테고리의 다른 글

[Grind75-LeetCode] Spiral Matrix JAVA (0)	2024.11.13
[Grind75-LeetCode] String to Integer (atoi) JAVA (0)	2024.11.12
[Grind75-LeetCode] Word Break JAVA (1)	2024.11.10
[Grind75-LeetCode] Sort Colors JAVA (1)	2024.11.09
[Grind75-LeetCode] Accounts Merge JAVA (1)	2024.11.08

현재글[Grind75-LeetCode] Partition Equal Subset Sum JAVA

kwang2134 님의 블로그

개발/ 알고리즘/깃허브 https://github.com/kwang2134

스프링, dfs, 오블완, programmers, 백준, grind75, 알고리즘, 웹 개발, blind75, BFS, 코딩테스트, neetcode, 티스토리챌린지, Java, spring, leetcode, 프로그래머스, 자바, spring data JPA, DP,

Today :
Yesterday :

kwang2134 님의 블로그