[프로그래머스] 의상

프로그래머스, 의상 문제 링크

종류별로 최대 1가지 의상만 착용할 수 있고, [의상의 이름, 의상의 종류]과 문자열로 주어진다. 따라서 해시 자료구조를 통해 각 의상 종류 별로 총 몇 개의 의상을 가지고 있는 지 분류하는 것이 첫 번째 순서이다.

즉, 의상의 종류 를 Key로 삼고, 해당 종류의 의상을 가지고 있을 떄 마다 1씩 카운트하면 된다.

그 다음으로 서로 다른 옷의 조합의 수를 어떻게 구할 것인가?가 핵심이 된다.

예시 1번을 생각해보자. 해시로 분류했다면 아래와 같이 값을 구해놓을 수 있다.

headgear: 2, eyewear: 1

여기서 곱셈 원리를 통해 한 종류의 옷에 대해 다음과 같은 경우의 수가 나온다.

1. 옷 종류 n개 중 하나를 선택
2. 아예 안 입는 경우

즉, headgear로 예를 들면 2개 + 1개(아예 안입는 경우) = 3개의 경우의 수가 나오는 것이다.

따라서 (headgear + 1) x (eyewear + 1) = 3 x 2 = 6 이 된다.

마지막으로 아무 옷도 입지 않는 경우는 제외해야 하므로, 정답은 6 - 1 = 5개가 된다.

전체 코드는 다음과 같다.

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        HashMap<String, Integer> hashMap = new HashMap<>();
        for (String[] cloth : clothes) {
            hashMap.put(cloth[1], hashMap.getOrDefault(cloth[1], 0) + 1);
        }
        
        for (int count : hashMap.values()) {
            answer *= (count + 1);
        }
        
        return answer - 1;
    }
}

곱셈 원리를 떠올릴 수 있는가?를 물어보는 문제인 것 같다.