[프로그래머스][Level2][Java] 위장

programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

문제풀이

까다로운 게 한가지 있었는데 모든 종류의 옷이 1개씩 있는경우 2n - 1으로 처리를 해주지 않을시 시간초과가 난다.

따라서 해쉬맵으로 옷의 종류를 구별하였고, 옷의 종류 해쉬 size가 clothes.length와 같다면 위와 같이 처리해줬다.

 

옷이 여러가지 일 경우 비교하는 수를 하나씩 증가시켜주면서 비교 해주었다.

끝이 얼굴2, 상의3, 하의2 의 경우 한개씩만 선택할때는 경우의수가 7이고,

2개일 때는 (얼굴, 상의) 2x3 = 6의 경우의 수가 나온다 이 모든 과정을 조합으로 뽑아내면서 결과값을 전역변수에

저장하여 return값으로 넘겨주었다.

 

코드

import java.util.*;
    
class Solution {
    static int[] keys;
    static int[] numbers;
    static int sum;
    
    public int solution(String[][] clothes) {
        sum = 0;
        
        HashMap<String,Integer> hm = new HashMap<>();
        for(int i=0; i<clothes.length; i++){
            if(hm.containsKey(clothes[i][1])){
                hm.put(clothes[i][1], hm.get(clothes[i][1])+1);
            }else{
                hm.put(clothes[i][1], 1);
            }
        }
        
        keys = new int[hm.size()];
        int index =0;
        for ( Map.Entry<String,Integer> entry : hm.entrySet() ) {
            keys[index++] = entry.getValue();
        }
        
        if(hm.size() == clothes.length) return (int)Math.pow(2,hm.size())-1;
        
        for(int i=1; i<=hm.size(); i++){
            numbers = new int[clothes.length];
            Arrays.fill(numbers, -1);
            combi(0,0,i,hm.size());
        }
        return sum;
    }
    
    public void combi(int cnt,int start, int limit, int size){
        if(cnt == limit){
            int index =1;
            for(int i=0; i<size; i++){
                if(numbers[i] == -1) break;
                index *= keys[numbers[i]];
            }
            
            sum += index;
            return;
        }
        
        for(int i = start; i<size; i++) {
			numbers[cnt] = i;
			combi(cnt+1, i+1, limit, size);
		}
    }
}