프로그래머스 - 위장

코드

1차 풀이

-만들 수 있는 모든 조합을 모두 뽑아서 계산을 하려했는데 1번 tc에서 차례로 메모리,시간 초과가 떠서 생각해보니 의상 종류가 최대 30개 라서 만들어질 수 있는 조합의 개수가 1억개가 넘어가기에 이 풀이로는 안되는 것을 알 수 있었다.

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

public class Solution {
    static int[] number;
    static boolean[] isVisited;
    static int[] comb;
    static int[] counts; // 의상 종류에 따른 개수 들어있는 배열
    static Map<String, Integer> m = new HashMap<>();
    static int answer = 0;
    public int solution(String[][] clothes) {
        // map 초기화
        for (int i = 0; i < clothes.length; i++) {
            m.put(clothes[i][1], 0);
        }
        // map 생성
        for (int i = 0; i < clothes.length; i++) {
            m.put(clothes[i][1], m.get(clothes[i][1]) + 1);
        }
        // int[] 배열로 넘겨두기
        counts = new int[m.size()];
        int index=0;
        for (String key : m.keySet()) {
            counts[index++] = m.get(key);
        }

        // 조합 생성을 위한 초기화
        isVisited = new boolean[counts.length + 1];
        number = new int[counts.length + 1];
        for (int i = 0; i < number.length; i++) {
            number[i] = i;
        }
        // 1개~N개 의 조합을 생성하도록
        for (int i = 1; i <= counts.length; i++) {
            comb = new int[i + 1];
            back(1, i);
        }
        return answer;
    }

    public static void back(int depth,int target) {
        if (depth == target + 1) {
            int tempAnswer=1;
            for (int i = 1; i < comb.length; i++) {
                tempAnswer *= counts[comb[i] - 1];
            }
            answer += tempAnswer;
            return;
        }
        for (int i = 1; i < number.length; i++) {
            if (!isVisited[i] && comb[depth - 1] < number[i]) {
                comb[depth] = number[i];
                isVisited[i] = true;
                back(depth + 1, target);
                isVisited[i] = false;
            }
        }
    }
}

2차 풀이

(각 의상 종류의 개수 + 1) 을 다 곱해나가서 간단하게 풀이 할 수 있음

package Programmers.CodingTestKit.해시.위장;

// getOrDefault 라는 Map 의 메소드를 이용하면 해당 key 값의 해당하는 값을 가져오거나 default 값으로 설정한다
import java.util.HashMap;
import java.util.Map;

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

결과

1차 풀이

2차 풀이

교훈

풀이를 설계할 때 최악의 경우에 해당하는 시간복잡도를 항상 생각하면서 설계하자