[프로그래머스] Lv.2 : 위장 - 자바[Java]

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

조합을 사용한 풀이 - 실패

HashMap을 사용하여 옷의 종류를 Key, 옷의 가짓수를 Value에 저장한 다음, 조합을 사용하여 모든 경우의 수를 구하였다. 옷의 종류가 n개가 있을 때, 한 종류의 옷만 입은 경우, 두 종류의 옷을 입은 경우, ... n개의 종류의 옷을 입은 경우의 수를 모두 더하여 답을 구했다.

하지만 테스트 1에서 시간초과가 나서 실패했다.

import java.util.*;

class Solution {
    
    public static int[] numbers;
    public static int answer = 0;
    public int solution(String[][] clothes) {
        HashMap<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < clothes.length; i++) {
            String kind = clothes[i][1];
            map.put(kind, map.getOrDefault(kind, 0) + 1);
        }
        
        numbers = new int[map.size()];
        int idx = 0;
        
        for (String kind: map.keySet()) {
            numbers[idx++] = map.get(kind); // 각 종류마다 가지고 있는 옷의 개수를 numbers에 저장한다
            answer += numbers[idx-1]; // 1종류의 옷만 입은 경우의 수를 더한다
        }
        
        // i개의 종류의 옷을 입은 경우의 수를 구하여 answer에 더한다
        for (int i = 2; i <= numbers.length; i++) {
            combination(0, 0, 1, i);
        }
        
        return answer;
    }
    
    public static void combination(int L, int start, int cnt, int size) {
        if (L == size) {
            answer += cnt;
            return;
        }
        
        for (int i = start; i < numbers.length; i++) {
            combination(L+1, i+1, cnt * numbers[i], size);
        }
    }
}

 

경우의 수를 구하는 간단한 방법

만약 headgear 종류의 옷이 a개, eyewear 종류의 옷이 b개인 경우 (a+1)*(b+1) - 1 을 하면 된다.

각 옷 종류 내에서 옷을 선택할 수도, 안할 수도 있으므로, 각 옷의 개수에 +1을 해야 하고

아무 것도 입지 않았을 경우의 수를 빼야 하므로 마지막에 1을 빼야 한다.

전체 코드

import java.util.*;

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

 

Stream 을 사용한 다른 풀이

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

class Solution {
    public int solution(String[][] clothes) {
        return Arrays.stream(clothes)
                .collect(groupingBy(p -> p[1], mapping(p -> p[0], counting()))) // Map<String, Long>
                .values() // Collection<Long>
                .stream() // Stream<Long>
                .reduce(1L, (x, y) -> x * (y + 1)) // Long
                .intValue() - 1;
    }
}

 

오른쪽이 Stream을 사용한 풀이