[Algorithm: 해시] 프로그래머스 <의상>

Hash 조합론 Java Programmers Lv.2

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=java

프로그래머스

 

---

 

문제 설명

의상의 종류별로 최대 1개씩 착용할 수 있고, 최소 1개는 입어야 한다. 가능한 서로 다른 의상 조합의 수를 구하는 문제다.

clothes	return
[["yellow_hat","headgear"],["blue_sunglasses","eyewear"],["green_turban","headgear"]]	5
[["crow_mask","face"],["blue_sunglasses","face"],["smoky_makeup","face"]]	3

 

 

---

 

핵심 아이디어: 곱의 법칙

처음엔 모든 조합을 직접 나열하려 할 수 있다. 하지만 의상 종류가 늘어날수록 경우의 수가 폭발적으로 증가한다. 수학적으로 접근하면 훨씬 단순하다.

각 종류에서 "안 입는" 선택지를 하나 추가하면,
종류별 선택지 수는 (해당 종류 의상 수 + 1)이 된다.
전체 경우의 수 = 각 종류별 선택지를 모두 곱한 값
여기서 모든 종류를 다 안 입는 경우 1가지를 빼면 정답이다.

예시 1 — headgear 2개, eyewear 1개

headgear 2개 + 안입기

×

eyewear 1개 + 안입기

=

(2+1) 3가지

×

(1+1) 2가지

=

6 전체

−

1 아무것도 안입기

=

5 정답

 

 

왜 (n+1)을 곱하는가?

각 종류에서 고를 수 있는 선택지를 표로 정리해보자.

headgear(2개) × eyewear(1개) 전체 조합표

headgear \\ eyewear

안입기

blue_sun
glasses

소계

안입기

둘 다 없음

blue_sun

1

yellow_hat

yellow_hat

yellow+blue

2

green_turban

green_turban

green+blue

2

소계

3

3

6-1=5

빨간 칸(둘 다 안입기)은 "최소 1개" 조건 위배 → 마지막에 -1로 제거

안입기를 선택지에 포함하는 이유:
"headgear를 안 입고 eyewear만 입는 경우"처럼 특정 종류를 생략하는 선택도 유효한 조합이다.
"안입기"를 각 종류에 1개 추가해야 이런 경우를 자연스럽게 계산할 수 있다.

 

 

HashMap으로 종류별 개수 세기

의상 배열을 순회하면서 종류(key)별 개수(value)를 HashMap에 저장한다.

예시 1 HashMap 구성 과정

headgear → 2 (yellow_hat, green_turban)

eyewear → 1 (blue_sunglasses)

예시 2 HashMap 구성 과정

face → 3 (crow_mask, blue_sunglasses, smoky_makeup)

종류가 하나뿐이므로: (3+1) - 1 = 3

for (int i = 0; i < clothes.length; i++) {
    if (!map.containsKey(clothes[i][1])) {
        map.put(clothes[i][1], 1);           // 처음 등장한 종류
    } else {
        int cnt = map.get(clothes[i][1]);
        map.put(clothes[i][1], cnt + 1);   // 이미 있는 종류 카운트 증가
    }
}

Java의 getOrDefault()를 활용하면 더 간결하게 작성할 수 있다.
map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0) + 1);

 

 

전체 풀이 흐름

1

clothes 배열을 순회해 종류별 의상 개수를 HashMap에 저장

2

answer = 1로 초기화 후, 각 종류의 (value + 1)을 차례로 곱하기

3

마지막에 answer - 1 반환 (아무것도 안 입는 경우 제거)

 

 

---

 

최종 코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> map = new HashMap<>();

        // 종류별 의상 개수 카운트
        for (int i = 0; i < clothes.length; i++) {
            if (!map.containsKey(clothes[i][1])) {
                map.put(clothes[i][1], 1);
            } else {
                int cnt = map.get(clothes[i][1]);
                map.put(clothes[i][1], cnt + 1);
            }
        }

        // 각 종류별 (개수 + 1) 곱하기 → +1은 "안입기" 선택지
        for (int value : map.values()) {
            answer *= (value + 1);
        }

        // 모든 종류를 안 입는 경우 제거
        return answer - 1;
    }
}

 

 

---

 

정리

HashMap 집계

clothes[i][1](종류)을 key로, 개수를 value로 저장. O(n)으로 종류별 집계 완료.

(n+1) 곱셈

각 종류에 "안입기" 선택지 1개를 추가. 종류별 독립 선택이므로 곱의 법칙 적용.

answer = 1로 초기화

곱셈 누적이므로 0이 아닌 1로 시작. 0으로 시작하면 모든 값이 0이 된다.

마지막 -1

"모든 종류를 다 안 입는" 경우 1가지는 최소 1개 조건 위배. 곱셈 결과에서 제거.

이 문제의 핵심은 완전탐색 없이 수학적으로 경우의 수를 구하는 것이다.
"안입기"를 선택지에 포함해 곱의 법칙을 적용하고, 마지막에 -1로 조건을 충족하는 패턴은
조합 문제에서 반복적으로 등장하는 중요한 기법이다.

 

 

 

* 이 포스팅은 Claude AI의 도움을 받아서 작성되었습니다.