owel의 블로그

프로그래머스 문제 풀이 - 의상 (Java)

문제 링크

프로그래머스 - 의상

풀이 아이디어

이 문제를 완전탐색으로 푼다면
각 종류의 의상마다 "입는다 / 안 입는다"를 선택해야 하므로
의상의 수가 최대 30개일 때 최악의 경우 2의 30승 ≈ 약 10억 개의 조합을 탐색해야 합니다.

그러나 문제의 조건상 실제 조합을 만들 필요 없이 조합의 개수만 구하면 되기에 수학적 연산을 통해 간단하게 풀 수 있습니다.

예시 데이터 [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]] 의 경우
종류별 의상 수는 headgear 2개, eyewear 1개입니다.

각 종류는 "안 입는 경우"를 포함해 (의상 수 + 1)가지 선택지가 있으므로 (2 + 1) × (1 + 1) = 6가지이고 문제의 조건상 아무 의상도 안 입는 경우는 있을 수 없으므로 안 입는 경우의 수 1을 빼면 총 5가지입니다.

조합을 일일이 구한다면 시간 초과가 날 것이지만
수학적으로 곱하기 연산을 통해 답을 구하는 것이 가능한 경우이므로 해당 방법으로 문제를 해결할 수 있습니다.

정답 코드

import java.util.Map;
import java.util.HashMap;

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