[프로그래머스,Level 2] 위장(JAVA 구현)

- 첫 풀이

  문제 자체를 읽었을 때, 조합을 구하는 문제라고 생각해 버려 접근을 잘못하였다. 열심히 삽을 푸다 다른 분들의 풀이를 조금 참고하게 되었다.

 

- 정답풀이

  이 문제는 사실 수학적인 '데카르트 곱'의 곱집합에 대한 문제라고 생각할 수 있다. 곱집합은 두 집합의 요소들로 만들 수 있는 경우의 수를 구하는 개념으로 쓰인다. 이 개념을 이용하기 전에 주의해야 할 점은 각각의 옷 종류에는 아예 선택하지 않는 경우 또한 존재하기 때문에 각 요소들의 개수 +1로 고려해주어야 한다. 

 

  입력 예제 1번의 경우 headgear가 2개, eyewear가 1개이지만, 안 입는 경우를 포함해 각각 3개 2개로 고려한다. 곱집합을 이용해 3 * 2 =6개가 되지만, 여기에는 두 집합의 요소로 만들 수 있는 모든 경우의 수가 포함되어 있다는 사실을 잊으면 안 된다. 앞서 안 입는 경우를 각각 추가해주었기 때문에 곱집합의 결과 (안 입기, 안 입기)라는 순서쌍 또한 존재한다. 그러나 문제에서는 최소 1벌의 옷은 입어야 한다는 제한사항이 존재하기 때문에 이 경우를 배제하게 되면 최종 공식은 (옷 종류 +1) * (옷 종류 +1) * (옷 종류 +1)...... -1이 된다.

 

  여기서 옷 종류를 카운팅 하는 방법은 level 1의 완주하지 못한 선수 문제에서 사용한 해시 맵의 getOrDefault() 메서드를 활용하게 된다.

import java.util.HashMap;
import java.util.Map.Entry;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        // 1. 옷 종류를 카운팅하기 위한 해시맵.
        HashMap<String,Integer> map = new HashMap<>();
        
        // 2. 옷 종류를 카운팅.
        for(String str[] : clothes)           
            map.put(str[1],map.getOrDefault(str[1],0)+1);
        
        // 3. 옷 종류의 수 + 안입는 경우 후, 곱집합  
        for(Entry<String,Integer> entry : map.entrySet())            
            answer *= entry.getValue()+1;
        
        // 4. 모두 안입는 경우 배제.
        return answer-1;
    }
}