💡 Hash 사용! (DP 이용한 풀이도 있음)

해시를 사용하긴하는데, 모든 조합의 경우의 수를 어떻게 구해야할까? 고민했다.

조합 알고리즘을 사용하려했는데, 시간복잡도가 '2^30*30'이라 이건 아니다싶었다.

결국 다른 사람이 어떻게 풀었는지 힌트를 살짝 얻었다.
특별한 알고리즘이 있는건 아니었고, 수학 공부할 때 자주 썼던 것 같은 풀이(?)가 있었다.

• 옷 종류마다 안 입는 경우 1개씩 추가해서, 각 종류의 가지수를 다 곱해주고, 마지막에 1(다 안입는 경우) 뺀다.

제출 코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        Map<String, Integer> count = new HashMap<>();
        
        for(int i=0; i<clothes.length; i++) {
            count.put(clothes[i][1], count.getOrDefault(clothes[i][1], 1) +1);
        }
        long temp = 1;
        
        for(Integer cnt : count.values()) {    
            temp *= cnt; 
        }
        answer = (int) (temp-1);
        return answer;
    }
}

이 코드에서 주의할 점!
처음에 long temp = 0;으로 초기화해뒀었는데, 답이 -1로만 나와서 어디가 잘못된건지 헤맸다.
0에는 어떤 수를 곱해도 0이다..엄청 기본적인건데, 사소한것도 잘 챙기자!

다른 풀이

찾아보니 DP를 사용해서도 푼다. 해당 코드도 공부해보자.

• dp[i][0]: 'i번째 옷은 안 입으면서 1~i-1번째 옷을 조합하는 경우의 수', dp[i][1]: 'i번째 옷을 입으면서 1~i-1번째 옷을 조합하는 경우의 수

Troubleshooting 1

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        Map<String, Integer> count = new HashMap<>();
        
        for(int i=0; i<clothes.length; i++) {
            count.put(clothes[i][1], count.getOrDefault(clothes[i][1], 1) +1);
        }
        
        //DP
        Integer[] cnt = new Integer[count.size()];
        count.values().toArray(cnt);
        
        for(int i=0; i<cnt.length; i++) {
            System.out.println(cnt[i]);
        }
        
        long[][] dp = new long[count.size()][2];
        dp[0][0] = 0;
        dp[0][1] = cnt[0];
        
        for(int i=1;i <dp.length; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-1][1];
            dp[i][1] = dp[i-1][0]*cnt[i] + dp[i-1][1]*cnt[i];
        }
        
        answer = (int) (dp[dp.length-1][0] + dp[dp.length-1][1]);
    
        return answer;
    }
}

문제

답이 이상하게 나온다.

원인

cnt의 값을 출력해보니, cnt에 값 자체가 잘못 들어가 있는 것 같다.

그런데 코드를 보면, cnt에서는 count.values().toArray(cnt);만 하고 있을 뿐이다.
그럼 count에 값이 잘못들어간걸로 판단된다.

dp를 사용하기 전의 로직에서는 해당 종류를 사용하지않는 경우가 있어서 해시맵 값의 디폴트를 1로 넣었는데, dp를 사용하려면 이렇게 초기화하면 안되고 실제 가지수를 넣어야한다.

해결

count.put(clothes[i][1], count.getOrDefault(clothes[i][1], 1) +1);
이 코드에서

count.put(clothes[i][1], count.getOrDefault(clothes[i][1], 0) +1);
이렇게 수정했다.

Troubleshooting 2

위의 상황에서 해결 코드만 수정한 상황

문제

테케가 틀리다. 근데 출력을 보니, 갯수는 알맞게 들어간 것을 확인할 수 있다.

원인

dp[0][0] = 0; 으로 초기화하면 어떤 값을 곱해도 0이되므로
dp[i][1] = dp[i-1][0]*cnt[i] + dp[i-1][1]*cnt[i];이 코드에서 처음에 값이 제대로 계산되지 않을것이다.

해결

dp[0][0] = 1; 로 초기화했다. (아무것도 선택하지 않는 경우도 경우의수로 우선 포함)
대신,
answer = (int) (dp[dp.length-1][0] + dp[dp.length-1][1] -1);로 수정하며, 마지막에 1을 빼주는 걸 추가했다. (아무것도 선택하지 않는 경우의 수 뺌)

제출 코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        Map<String, Integer> count = new HashMap<>();
        
        for(int i=0; i<clothes.length; i++) {
            count.put(clothes[i][1], count.getOrDefault(clothes[i][1], 0) +1);
        }
        
        //DP
        Integer[] cnt = new Integer[count.size()];

        count.values().toArray(cnt);

        long[][] dp = new long[count.size()][2];
        dp[0][0] = 1;
        dp[0][1] = cnt[0];
        
        for(int i=1;i <dp.length; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-1][1];
            dp[i][1] = dp[i-1][0]*cnt[i] + dp[i-1][1]*cnt[i];
        }
        
        answer = (int) (dp[dp.length-1][0] + dp[dp.length-1][1] -1);
    
        return answer;
    }
}

공부한 사항

• toArray()