[프로그래머스] 의상 (Hash)

문제 소개

오늘 풀었던 프로그래머스 - 의상 문제를 정리합니다.

이 문제는 의상들이 주어졌을 때, 각 의상 종류별로 하나씩 착용하거나 착용하지 않는 경우를 고려하여
서로 다른 옷 조합의 수를 구하는 문제입니다.
단, 최소한 하나 이상의 의상을 입어야 합니다.

문제 링크: 위상 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

• 의상 종류별로 몇 개의 선택지가 있는지를 센다
  예) headgear에 2개 옷 존재 → (선택 안 함 포함) 3가지 선택
• 각 종류별 선택지 개수 + 1 후 곱해 모든 조합의 수를 구한다
• 단, 모든 종류를 '선택하지 않는 경우' (모두 안 입는 경우)는 제외해야 하므로 최종 결과에서 1을 뺀다

---

해결 과정 및 코드

핵심 아이디어

1. 종류별 의상 개수 → cnt
2. 해당 종류에서 입을지 말지를 포함한 경우의 수 = cnt + 1
3. 전체 경우의 수 = 모든 (cnt + 1)을 곱한 값 - 1

코드

시간 복잡도 : O(N) (그룹화 후 덧셈 및 곱셈)

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int solution(String[][] clothes) {
        return Arrays.stream(clothes)
             	// 1. 옷을 종류별(얼굴/상의/하의/겉옷)로 그룹화하고, 각 종류별 옷의 개수를 센다.
                .collect(Collectors.groupingBy(c -> c[1], Collectors.summingInt(c -> 1))) // summingInt 각 종류별 옷 개수를 셈
                .values() // Map 객체에 저장된 값들만 모은 Collection을 반환
                .stream()
                // 2. 각 종류별 옷 개수에 1을 더해 선택 여부를 포함한 경우의 수를 구함
                .map(cnt -> cnt + 1)
                // 3. 모든 종류의 경우의 수를 곱한 후, 전부 안 입는 경우(모든 종류에서 '안 입기' 선택)를 제외함
                .reduce(1, (a, b) -> a * b) - 1;
    }
}