프로그래머스 - 의상

일단 해쉬 자료구조가 필요한 문제고, 풀이를 위한 아이디어가 또 있어야 한다.

첫 번째 풀이 (오답)
의상 종류를 선택하는 경우의 수를 구해서, 뽑은 의상 종류들로 만들 수 있는 옷의 조합을 구한다.
ex) 상의, 신발을 뽑았으면, 상의 갯수 x 신발 갯수
이 때, 의상 종류를 0개 뽑는 조합의 옷의 조합 수부터 종류를 n개 뽑는 조합의 옷의 조합 수를 모두 더한다.
따라서 옷의 종류의 갯수를 저장하기 위해 해쉬맵과, 옷의 종류를 뽑는 경우의 수를 구하기 위해 백트래킹 알고리즘을 사용했다.

import java.util.*;
class Solution {
    static int answer = 0;
    static HashMap<String, Integer> map;
    static String[] syurui;
    static String[] getArr;
    static int[] isUsed;
    public int solution(String[][] clothes) {
    	//key: 의상종류, value: 해당 종류의 옷 갯수
        map = new HashMap<>();
        for(int i = 0; i < clothes.length; i++){
            if(map.containsKey(clothes[i][1])){
                map.put(clothes[i][1], map.get(clothes[i][1])+1);
            }else{
                map.put(clothes[i][1], 1);
            }
        }
        syurui = new String[map.size()];
        getArr = new String[map.size()];
        isUsed = new int[map.size()];
        int p = 0;
        for(String s : map.keySet()){
            syurui[p++] = s;
        }
        for(int i = 1; i <= map.size(); i++){
            //clothes종류 중 i개 뽑기
            bt(0, i);
        }
        return answer;
    }
    static void bt(int now, int range){
        if(now == range){
            //i개만큼 뽑았으면
            //뽑은 옷의 종류들로 조합한 경우의수 구하기
            int sum = map.get(getArr[0]);
            for(int i = 1; i < range; i++){
                sum *= map.get(getArr[i]);
            }
            answer += sum;	//구한 후 answer에 추가
        }
        for(int i = 0; i < range; i++){
            if(isUsed[i] == 1){
                continue;
            }
            getArr[now] = syurui[i];
            isUsed[i] = 1;
            bt(now+1, range);
            isUsed[i] = 0;
        }
    }
}

제출 결과는 처참했다. 일단은 개선을 시도해보았는데, 어차피 시간초과 때문에 백트래킹 알고리즘은 아닌 것 같아서 포기하고 다른 풀이를 찾아봤다.

해답
그냥 문제에 주어진 상황에서 조합을 구하는 방법을 잘 생각해내야 한다.
각 옷의 종류마다 0개 고르는 경우 ~ 모두 고르는 경우를 다 곱해주고, 옷을 단 하나도 선택하지 않는 경우의 수를 하나 빼준 것이 답이다.

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < clothes.length; i++){
            if(map.containsKey(clothes[i][1])){
                map.put(clothes[i][1], map.get(clothes[i][1]) + 1);
            }else{
                map.put(clothes[i][1], 1);
            }
        }
        for(String s : map.keySet()){
            answer *= map.get(s) + 1;	//해당 옷의 종류의 옷 갯수 + 옷을 0개 고른 경우
        }     
        return answer-1;	//answer - 옷을 단 하나도 선택하지 않는 경우의 수
    }
}

참고
https://coding-grandpa.tistory.com/78