[프로그래머스] 위장

프로그래머스 <위장>

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

코딩테스트 연습 - 위장

---

<위장>

스파이가 가진 의상들이 담긴 clothes 배열이 주어졌을 때, 서로 다른 옷의 조합 수를 반환하여라.

이때, 스파이는 하루에 최소 한 개의 의상은 입는다.

---

문제 해결

의상의 종류가 몇 개가 들어올지 모르고 어떤 의상의 종류가 들어올지 모르기 때문에 HashMap을 사용하였다.

 

일단 의상 종류에 따라 몇 개의 의상이 있는지 알아야 하기 때문에 clothes 배열을 보고 HashMap을 채워줘야 한다.

이때 HashMap은 의상의 종류가 key이고 해당 종류의 개수가 value이다.

 

조합 문제이기 때문에 combination 함수를 구현해서 풀려고 했다.

---

실패 코드

import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        HashMap<String, Integer> camouflage = new HashMap<>();
        int len = clothes.length;
        
        for(int i = 0; i < len; i++){
            if(!camouflage.containsKey(clothes[i][1])){
                camouflage.put(clothes[i][1], 1);    
            }else{
                int temp = camouflage.get(clothes[i][1]);
                camouflage.put(clothes[i][1], temp + 1);
            }
        }
        int have_len = camouflage.size();
        int[] elem = new int[have_len];
        int idx = 0;
        for(Integer v : camouflage.values()){
            elem[idx] = v;
            idx++;
        }
        
        for(int i = 1; i <= have_len; i++){
            answer += combination(elem, 0, have_len, i, 1);
        }
        return answer;
    }
    
    public static int combination(int[] elem, int start, int n, int r, int result){
        int answer=0;
        if(r == 0){
            return result;
        }
        for(int i = start; i < n; i++){
            answer += combination(elem, i+1, n, r-1, result*elem[i]);
        }
        return answer;
    }
}

 

elem 배열은 의상의 종류의 개수 크기의 int 형 배열로 각 의상 종류의 의상 개수를 값으로 갖는다.

combination(int[] elem, int start, int n, int r, int result) 함수는

start 부터 시작해서 n개 중에 r개를 뽑은 경우이다. 이때 result는 스파이가 의상을 입을 수 있는 조합의 수를 의미한다.

 

이렇게 풀면

test 1번이 통과하지 못한다.

질문 게시판을 보니 test 1번은 30 종류의 옷이 1개씩 있을 경우이다. 그래서 2^n-1이 정답이라고 한다.

위의 코드처럼 풀면 시간초과가 날 수밖에,,

---

질문 게시판에서 힌트를 얻어서 아래와 같이 다시 풀었다.

 

옛날에 배웠던 확률과 통계에서 경우의 수로 생각해보면

의상의 종류의 의상 수 + 1 = 각 의상 수를 입는 경우 + 입지 않는 경우

이렇게 생각할 수 있다.

그래서 각 의상의 종류의 의상 수에 +1을 해서 모두 곱하면 스파이가 옷을 입는 경우의 수를 구할 수 있다.

이때 -1을 해줘야 하는데 모든 의상의 종류를 입지 않는 경우가 1번 있을 수 있기 때문이다.

 

예를 들어보면 a 종류가 2개, b 종류가 4개, c 종류가 3개, d 종류가 6개라고 했을 때,

(2 +1) = a 종류의 옷을 입는 경우 2와 안 입는 경우 1을 더한 값.

(2 +1)(4 +1)(3 +1)(6 +1) - 1 = a, b, c, d 종류의 옷을 조합해서 입는 경우(이때 각 종류의 옷은 입을 수도 있고 안 입을 수도 있다.) -- (모든 종류 a, b, c, d를 입지 않는 경우)

 

성공 코드

import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        HashMap<String, Integer> camouflage = new HashMap<>();
        int len = clothes.length;
        
        for(int i = 0; i < len; i++){
            if(!camouflage.containsKey(clothes[i][1])){
                camouflage.put(clothes[i][1], 1);    
            }else{
                int temp = camouflage.get(clothes[i][1]);
                camouflage.put(clothes[i][1], temp + 1);
            }
        }
        for(Integer v : camouflage.values()){
            answer *= (v+1);
        }
        answer --;
        return answer;
    }
}

---

결과

---