[프로그래머스 / Level2] 위장 (Java)

문제

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

코딩테스트 연습 - 위장

 

풀이

스파이는 전날 옷 조합에 변화를 줘서 다음날 입어야 한다.
ex) 같은 종류의 다른 의상으로 변경하거나, 아예 다른 종류의 의상을 새로 하나 추가하기

옷의 조합은 최소 한개의 의상을 포함해야 한다.

스파이가 가진 의상이 담긴 2차원 배열에서 같은 종류의 의상은 1가지만 착용할 수 있음
ex) 같은 "headgear" 종류의 의상 "yellowhat"과 "green_turban"을 동시에 착용할 수 없음.

Key : 의상 종류, Value : 의상의 이름 형태의 HashMap을 생성해서 활용한다.

=> 서로 다른 옷 조합의 수 : 각 의상을 하나씩 입은 경우의 수 + 서로 다른 종류의 의상을 함께 입는 경우의 수

테스트 케이스 = String[3][2]	{ {"yellowhat", "headgear"}, {"bluesunglasses", "eyewear"}, {"green_turban", "headgear"} }
가진 의상 = 3개	headgear : yellowhat, green_turban eyewear : bluesunglass
옷 조합 = 5개	[headgear] = 2 1. yellowhat 2. green_turban [eyewear] = 1 3. bluesunglass [headgear + eyewear] = 2 * 1 = 2 4. yellowhat + bluesungalss 5. green_turban + bluesunglass

 

위 옷 조합에서 headgear가 하나도 없는 경우, eyewear가 하나도 없는 경우도 존재하기 때문에 단순히 {headgear종류개수(2) * eyewear종류개수(1) = 2} 식으로는 원하는 결과 5를 얻을 수 없다. 해당 식은 모든 종류의 옷을 적어도 1개씩 입은 조합의 개수를 구하는 것이다. 그러나, 본 문제에서는 최소 1개의 의상을 걸치면 의상 조합으로 인정하기 때문에, 어떤 종류의 의상을 하나도 걸치지 않은 경우도 조합에 포함시킬 수 있다. 즉, 모든 의상 종류를 필수로 하나씩 입을 필요가 없다는 뜻. 위 테스트케이스를 예시로 했을 때, {headgear종류로 가능한 조합의 수 * eyewear종류로 가능한 조합의 수 -1 = 5} 식으로 하면 제대로된 결과가 구해진다. 마지막에 -1을 하는 이유는 [headgear를 입지 않음 & eyewear를 입지 않음] 의 옷 조합으로 아무것도 입지 않은 건 옷 조합으로 인정하지 않기 때문에 해당 경우의 수를 뺀 것이다.

 

가능한 조합들을 반환하는 게 아니라 가능한 조합의 개수를 반환하는 것이기 때문에 옷 종류별 개수를 구한 뒤 경우의 수 정수 계산만으로 쉽게 답을 구할 수 있다.

 

코드

import java.util.HashMap;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;     // 0 *= i 방지용

        // 옷 종류별 개수
        HashMap<String, Integer> map = new HashMap<>();
        for (String[] clothe : clothes) {
            System.out.println(clothe[1]);
            map.put(clothe[1], map.getOrDefault(clothe[1], 0) + 1);
        }
        System.out.println(map);

        // 모든 옷 조합의 수
        for (Integer i : map.values()) {
            answer *= i.intValue() + 1;
        }

        return answer - 1;    // 모든 종류의 옷을 입지 않은 경우 빼기
    }
}