알고리즘 프로그래머스 - 위장

https://programmers.co.kr/learn/courses/30/lessons/42578?language=java

문제 풀이

의상의 이름, 의상의 종류 배열로 입력이 들어올때

의상의 종류별로 옷을 선택해서 입는 경우의 수를 계산하는 문제이다.

문제를 접하고
옷을 1개 입을때
옷을 2개 입을때
옷을 n개 입을때

로 나누어서 풀어야 한다 생각했고

dfs로 문제를 풀다보니 문제가 굉장히 어렵게 느껴졋다.

해당 솔루션으로 구현한 코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

class Solution {
    int answer = 0;

    public int solution(String[][] clothes) {

        HashMap<String, Integer> map = new HashMap<>();

        for(int i = 0 ; i < clothes.length ; i++){

            String key = clothes[i][1];

            if(map.get(key) == null){
                map.put(key, 1);
            }else{
                map.put(key, map.get(key)+1);
            }
                
        }

        int mapSize = 0;
        
        ArrayList<Integer> list = new ArrayList<Integer>();

        Iterator<String> iterator =  map.keySet().iterator();

        while(iterator.hasNext()){
            String key = iterator.next();
            int thisSize = map.get(key);
            
            list.add(thisSize);
            mapSize++;
        }

        for(int i = 1 ; i<= mapSize ; i++){
            choice(0, i, list, 1);   
        }

        
        return answer;
        
    }

    void choice(int current, int count, ArrayList<Integer> list, int select){

        if(count == 0){
            answer += select;
            return;
        }

        for(int i = current ; i < list.size() ; i++){
            int thisSelect = list.get(i);
            ArrayList<Integer>newList = (ArrayList<Integer>) list.clone();
            newList.remove(i);

            choice(i, count-1, newList, select*thisSelect);
        }

    }

}

풀고나서 다른분들의 풀이가 너무 간단해서 찾아본 결과...

종류별 의상의 갯수를 구한다음
해당 종류의 의상을 안입는 경우의수를 더해서 계산을 하는 방식을 보았고.....

해당 방식은 너무나 간단했다.

import java.util.HashMap;

class Solution {

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

        HashMap<String, Integer> map = new HashMap<>();

        for(int i = 0 ; i < clothes.length ; i++){

            String key = clothes[i][1];

            map.put(key, map.getOrDefault(key,0) + 1);
                
        }

        int caseCount = 1;
        
        for(int value : map.values()){
            caseCount *= (value +1);
        }

        answer = caseCount -1;
        
        return answer;
        
    }

}

각 의상의 갯수 +1(해당 의상종류를 안입는 경우...)를 더해서 전부 곱해주고
모든 의상을 안입는 경우를 빼주면 되는것이엇던것...

대충 수학 머리가 없는편....