프로그래머스 알고리즘 고득점 Kit - [Lv.2] 의상 (Java)

문제 출처 - 링크

알고리즘 분류

• 해시

📋 문제 요약 설명

• 코니는 하루에 최소 한 개의 의상은 입습니다.
• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 서로 다른 옷의 조합의 수를 return 하도록 한다.

💡 알고리즘 설계 / 접근 방법

• 경우의 수를 조합으로 풀면 된다.

  1. 안 입는 경우를 포함해서 옷의 종류 당 개수를 모두 곱한다.

     • headgear : 총 3가지 (안입음, yellow_hat, green_turban)
     • eyewear : 총 2가지 (안입음, blue_sunglasses)

  2. 옷의 종류를 모두 안 입는 경우 1가지를 뺀다.

✅ 풀이

시간 복잡도 → O(N + K)

대부분의 경우, K << N 이므로 사실상 시간 복잡도는 O(N)에 가깝다.

1. 첫 번째 for문 : 배열을 한 번 순회 → O(N)
   1. N : 옷의 총 개수 (clothes.length)
2. 두 번째 for문 : 루프를 K번 반복 → O(K)
   1. K : 옷의 종류 수 (map.keySet().size())

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // 종류별로 몇 개씩 있는지 저장
        for(String[] cloth : clothes) {
            String key = cloth[1]; // 옷 종류
            map.put(key, map.getOrDefault(key, 0) + 1); // map(옷 종류, 옷 개수)
        }
        
        // 옷 종류가 1개일 때
        if(map.keySet().size() == 1)
            return clothes.length;
        
        int answer = 1;
        for (String key : map.keySet()) {
            // 서로 독립적인 선택을 하는 경우, 경우의 수는 곱한다는 조합의 기본 원리
            answer *= (map.get(key) + 1); // key : 각 종류마다 옷 개수, +1 : 안 입는 경우
            // headgear : 총 3가지 (안입음, yellow_hat, green_turban)
            // eyewear: 총 2가지 (안입음, blue_sunglasses)
        }               
        answer -= 1; // 모두 안 입는 경우 1개 제거
        
        return answer;
    }
}