[프로그래머스/Java] Lv.2 - 의상

Lv.2 - 의상

문제 바로가기

1. 문제 요구사항

• 입력: 의상의 이름과 종류가 담긴 2차원 배열 clothes. (예: [["yellow_hat", "headgear"], ...])
• 규칙:
  • 각 종류(카테고리)별로 최대 1가지 의상만 착용할 수 있다. (모자 2개 동시 착용 불가)
  • 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나 추가로 착용한 의상이 있다면 서로 다른 조합으로 간주한다.
  • 최소 한 개의 의상은 반드시 입어야 한다.
• 출력: 서로 다른 옷의 조합의 수.

2. 접근 방식 (Algorithm)

이 문제는 코딩 구현력보다는 "어떻게 식을 세울 것인가"가 핵심이다.

1) 데이터 전처리 (HashMap)

주어진 배열에서 중요한 정보는 '의상의 종류'와 '각 종류별 개수'다.
의상의 이름(예: yellow_hat) 자체는 중요하지 않다.
따라서 HashMap<String, Integer>를 사용하여 (종류 : 개수) 형태로 데이터를 정리한다.

2) 경우의 수 공식 도출 (핵심)

단순히 종류별 개수를 곱하면 안 된다. 어떤 종류의 옷은 "입지 않을 수도" 있기 때문이다.
따라서 각 종류별로 (안 입음)이라는 선택지를 가상의 아이템처럼 하나씩 추가해줘야 한다.

• 공식: $(\text{A종류 개수} + 1) \times (\text{B종류 개수} + 1) \times \dots$
  • 여기서 +1은 해당 종류를 입지 않는 경우를 의미한다.

3) 예외 처리

위 공식대로 계산하면, 모든 종류에서 '안 입음'을 선택한 경우(알몸 상태)가 포함된다.
문제 조건에서 "최소 한 개의 의상은 입는다"고 했으므로, 마지막에 1을 빼준다.

3. 코드

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        int n = clothes.length;
        
        Map<String, Integer> map = new HashMap<>();
        for(int i=0; i<n; i++) {
            map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0)+1);
        }
        
        for(int value : map.values()) {
            answer *= value+1;
        }
        
        return answer-1;
    }
}

3. 느낀점 & 배운점

1. 코딩보다 수학적 사고가 먼저

처음에는 조합(Combination)을 직접 구현하려고 했으나, 문제의 특성을 파악하니 단순한 수학 공식으로 $O(N)$만에 풀 수 있는 문제였다. 무작정 키보드에 손을 올리기 전에, 수학적으로 단순화할 수 있는 방법이 있는지 먼저 고민하는 습관을 가져야겠다.

2. Map.values() 활용

이전에는 map.entrySet()을 습관적으로 사용했는데, 이번 문제처럼 Key(의상 종류 이름)가 필요 없고 Value(개수)만 필요한 경우에는 map.values()를 사용하는 것이 코드를 훨씬 직관적이고 깔끔하게 만든다는 것을 배웠다.

3. 관점의 전환 (투명 옷)

"안 입는 경우"를 복잡하게 예외 처리하는 것이 아니라, "투명 옷을 하나 더 가지고 있다"고 생각하고 곱셈으로 처리하는 발상이 인상적이었다. 경우의 수 문제에서 자주 쓰이는 테크닉이니 기억해둬야겠다.

---

Tags: #Java #Algorithm #Programmers #Hash #Math