알고리즘(위장)

[위장]

 

* 로직

• 우선 종류에 맞게끔 옷들을 해쉬맵에 보관한다
• 각각 종류에는 옷들의 개수가 존재한다
  
  
• 단순하게 생각해보면 결국 모든 경우의 수를 구한다
  • nC1 + nC2 + ... + nCr (최소 한벌은 입어야 하기 때문에)
• 여기서 좀 더 발전시켜 생각해보면
  
  • (각 종류에 존재하는 옷의 개수 + 1)을 함으로써 해당 종류의 옷을 선택하지 않은 경우를 추가할 수 있다
  • (A종류의 옷+1) * (B종류의 옷+1) * (C종류의 옷+1)을 하게되면 3가지 종류에 존재하는 옷들로 만들 수 있는 모든 경우의 수를 구할 수 있게된다
  • 주의할 점은, 모두 옷을 선택하지 않은 경우가 포함되기 때문에 -1을 해줌으로써 답을 구할 수 있게된다

 

//위장
import java.io.*;
import java.util.*;

class Solution {
    static int result;
    static ArrayList<Integer> arrayList;
    
    public int solution(String[][] clothes) {
        int answer = 0;
        HashMap<String, ArrayList<String>> hashmap = new HashMap<>();
        for(String[] input : clothes) {
            if(hashmap.size() == 0) {
                ArrayList<String> list = new ArrayList<>();
                list.add(input[0]);
                hashmap.put(input[1], list);
            }
            
            else {
                
                //이미 키가 존재한다면
                if(hashmap.containsKey(input[1])) {
                    ArrayList<String> list = hashmap.get(input[1]);
                    list.add(input[0]);
                    hashmap.put(input[1], list);
                }
                
                //그렇지 않다면
                else {
                    ArrayList<String> list = new ArrayList<>();
                    list.add(input[0]);
                    hashmap.put(input[1], list);
                }
            }
        }
        
        result = 1;
        for(String key : hashmap.keySet()) {
            result *= hashmap.get(key).size() + 1;
        }     
                
        return answer = result-1;
    }   
}