[프로그래머스] 해시 - 위장

문제를 읽고 예제를 이해하고 

예제 풀이법 대로 고민을 한 다음 풀이를 작성했다.

 

예를 들어, 상의, 하의, 겉옷이 각각 3,2,1 개씩 있다면

3+2+1 + 3*2 + 3*1 + 2*1 + 3*2*1 이런 식으로 모든 수를 계산하려 하였다.

 

	static String result="";
	
	static int solution(String[][] clothes) {
        int answer = 0;
        
        // 옷의 종류와 이름이 너무 길어 두개의 해시맵을 이용하여 character와 int로 처리
        HashMap<String,Character> typeMap=new HashMap<>();
        HashMap<Character,Integer> clothMap=new HashMap<>();
        
        int charnum=97;
        
        //초기화 부분
        for(int i=0;i<clothes.length;i++) {
        	if(typeMap.containsKey(clothes[i][1])) {
        		char key=typeMap.get(clothes[i][1]);
        		int val=clothMap.get(key);
        		clothMap.replace(key, val+1);
        	}
        	else {
        		typeMap.put(clothes[i][1], (char)charnum);
        		clothMap.put(typeMap.get(clothes[i][1]),1);
        		charnum++;
        	}
        }
                
        char[] arr=new char[typeMap.size()];
        boolean[] visited=new boolean[typeMap.size()];
        int index=0;
        
        //combination함수에 쓰일 arr 생성 함수
        Set<Character> keySet=clothMap.keySet();
        Iterator<Character> it=keySet.iterator();
        while(it.hasNext()) {
        	arr[index++]=it.next();
        }
        
        for(int i=1;i<=typeMap.size();i++) {
        	result="";
    		int mul=1;
        	combination(arr,visited,0,typeMap.size(),i);
        	for(int j=0;j<result.length();j++) {
        		if(result.charAt(j)==' ') {
        			answer+=mul;
        			mul=1;
        			continue;
        		}
        		mul *= clothMap.get(result.charAt(j));
        	}
        }
        
        return answer;
    }

정답을 string 형태로 반환받아 계산하도록 하였지만.. 4개의 문제에서 시간 초과 에러..

처음에 시간 초과가 반복문에서 난다고 생각해서 고쳐보고..

combination도 재귀방법으로 바꿔보았지만.. 해결되지 않음.. 

 

다른 블로그를 보고 깨닳았다.

옷은 입거나, 입지 않거나.. 단 모두 입지 않는 경우는 없다.

이것을 계산식으로 바꾸면

 

(3+1) * (2+1) * (1+1) -1

마지막의 -1은 모두 입지 않는 경우이다..

 

public int solution(String[][] clothes) {
    	int answer = 1; 

    	HashMap<String, Integer> map = new HashMap<>();
    	
    	for(int i = 0; i < clothes.length; i++) {
    		if(map.get(clothes[i][1]) == null)
    			map.put(clothes[i][1], 1);
    		else
    			map.put(clothes[i][1], map.get(clothes[i][1]) + 1);
    	}
    	
    	for(String keys: map.keySet()) {
    		answer *= (map.get(keys) + 1);
    	}
        
    	answer -= 1;
        
        return answer;
    }

이렇게 간단하게 해결 가능!