[programmers] 의상 - 해시, 조합론

1. 서론

해시 + 조합으로 금방 풀리겠지라고 접근했다가 고려하지 못한 케이스 때문에 시간을 오래 잡아 먹었던 문제이다.

 

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

2. 본론

이 문제의 핵심은

(1) 옷 여러벌을 같은 종류에서 고르면 안됨 (중복 x)

(2) 1, 2, ... n 가지 입는 경우의 수를 더해야 함 (조합)

 

으로 해시 + 조합론 을 활용한 문제풀이가 적합하다.

 

때문에 필자는 다음과 같이 구조를 짜보았다.

(1) n과 r 을 파라미터로 갖는 조합 함수 `comb()` 구현

(2) 입력 clothes 배열 for 문 조회 -> HashMap 카테고리 별 count 추가

(3) 1 ~ 카테고리 종류수 (HashMap.size()) 만큼 for 문 반복

     (3.1.) `comb(총개수, i)` 결과에 합산

     (3.2.)  HashMap value > 1 이고,  `comb(value, i)` 를 결과에서 뺌 - 같은 종류에서의 i 개 선택 제거

(4) return 결과

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        HashMap<String, Integer> hm = new HashMap<>();
        
        for (String[] arr : clothes){
            String kind = arr[1];
            int value = hm.getOrDefault(kind, 0);
            
            if (value == 0){
                hm.put(kind, 1);
            }else{
                int updated = value + 1;
                hm.put(kind, updated);    
            }
            
        }
        
        // 모든 옷 개수 산출
        int total = 0;
        
        for (int value : hm.values()){
            total += value;
        }
        
        // 종류 총 개수 산출
        int kindAmt = hm.size();
        
        // total 중에 1 -> 총 종류수까지 선택하는 조합 합산 
        for (int i=1; i<= kindAmt; i++){
            
            // 1개만 선택할 땐 조합 더하기
            if (i==1){
                answer += comb(total, i);
            } 
            
            // 1 이상 일 때는 value 가 1이상 (중복 가능성 있는 애들) 빼기
            else{
                answer += comb(total, i);
                
                for (int value : hm.values()){
                    if (value == 1 || value < i) continue;
                    
                    answer -= comb(value, i);
                }
            }
        }
                
        return answer;
    }
    
    public int comb(int n, int r){
        long child = 1; long momA = 1; long momB = 1;
        
        for (int i=n; i>0; i--){
            child *= i;
        }
        
        for (int j=r; j>0; j--){
            momA *= j;
        }
        
        for (int k=n-r; k>0; k--){
            momB *= k;
        }
        
        int result = (int) (child / (momA * momB));
        return result;
    }
}

 

이 로직에선 다음 케이스가 반영되지 못했다.

i = 3 일때, 동일 종류 2개 + 다른 종류 1개 케이스

ex. A | B | C -> A1, A2, C1 (x)

      2 | 2 | 2 

 

조합론을 활용한 접근법은 옳았으나, 뽑는 개수(r) 별로 더하는 방법이 적절하지 않았다.

문제 내에서 의류 종류 별로 독립적인 경우의 수 이기 때문에, 각 종류 별 경우의 수를 곱해주면 0개 ~ 최대 종류수 까지 뽑는 모든 경우의 수가 나오게 된다. 여기에 모든 종류에서 안뽑히는 경우를 한번 빼주면 된다.

 

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> hm = new HashMap<>();
        
        for (String[] arr : clothes){
            String kind = arr[1];
            int value = hm.getOrDefault(kind, 0);
            
            if (value == 0){
                hm.put(kind, 1);
            }else{
                int updated = value + 1;
                hm.put(kind, updated);    
            }
            
        }
        
        for (int value : hm.values()){
            answer *= value + 1;
        }
                
        return answer -1;
    }
}

 

3. 결론

알고리즘 문제를 풀 때마다 처음 설계에서 부분 부분의 테스트 케이스가 틀릴 경우 반례만 찾게 되는거 같다. 우연히 맞아 떨어지는 설계를 하진 않았는지 검토하는 습관을 들여야 할 것 같다.