[프로그래머스] 연습문제 - 위장

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

import java.util.HashMap;


class Solution {
    
    private int answer = 0;
    public synchronized int solution(String[][] clothes) {
        answer = 0;
        HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i < clothes.length; i++) {
            String a = clothes[i][0];
            String b = clothes[i][1];
            int count = 1;
            if(map.containsKey(b)){
                count = map.get(b);
                map.put(b, ++count);
            }else{
                map.put(b, count);
            }
        }

        int total = map.size();
        int [] arr = new int[total];
        int i = 0;
        for (Integer value : map.values()) {
            arr[i++] = value;
        }

        int p = 1;
        boolean [] visited = {false, false, false};

        for (int k = 1; k <= arr.length; k++) {
            //    System.out.println("\n" + arr.length + " 개 중에서 " + k + " 개 뽑기");
            answer = combination(arr, visited, 0, arr.length, k);
        }
        return answer;
    }

    int combination(int[] arr, boolean[] visited, int start, int n, int r) {
        if(r == 0) {
            int sum = getSum(arr ,visited, n);
            answer += sum;
            return answer;
        }

        for(int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
        return answer;
    }

    int getSum(int[] arr, boolean[] visited, int n) {
        int sum=0;
        int mul=1;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                //System.out.print(arr[i]);
                mul*=arr[i];
            }
        }
        sum+=mul;
        return sum;
    }
}

- 처음에 이렇게 풀었으나, 테스트 중간중간에 런타임 에러가 발생했었다 ...

 

문제 요약

- 의상의 종류와, 이름이 2차원 배열로 주어진다.

- 의상의 수는 1개 이상, 30개 이하

- 같은 이름을 가진 의상은 존재하지 X

- 모든 문자열의 길이는 1 이상 20 이하인 자연수, 알파벳 소문자 또는 _ 로만 이루어져 있음.

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

 

처음에 생각했던 방법

- 해시맵에다가 종류별로 의상의 개수가 몇 개 있는지 담아둔다.

- 총 N종류가 있다고 했을 때 1가지 종류만 입을때의 경우의 수, 2가지 종류 입을때의 경우의 수 ... N가지 종류 입을 때의 경우의 수를

다 구하여서 합하고, sum 을 리턴한다.

 

❔ 문제점

- combination 을 다 구하지 않아도 되는 경우 - 예를 들어서 종류당 1개씩밖에 없는 경우 비효율적인 방법일 수도 있다.

- static 변수로 answer 를 놓고 이에 더해나가는 방식인데, 채점 환경에서 이렇게 static 변수를 설정하는게 맞지 않는 것 같음 ... (?)

 

✨ 다른 사람의 답변 1

    public static int solution(String [][] clothes){
        int answer = 1;

        HashMap<String, Integer> map = new HashMap<>();
        for (String[] clothe : clothes) {
            String key = clothe[1];
            if (!map.containsKey(key)) {
                map.put(key, 1);
            } else {
                map.put(key, map.get(key) + 1);
            }
        }

        for (Integer integer : map.values()) {
            answer *= integer + 1;
        }
        return answer - 1;
    }

- Map 에다가 옷의 종류 : 개수 와 같은 형식으로 담는 것 까지는 동일하다.

 

A - 3

B - 4

C - 1

과 같이 옷과 개수의 맵이 있다면, 세 가지를 모두 다 조합해서 옷을 고르는 경우의 수는 3 * 4 * 1 이고, 만약 하나라도 입지 않아도 된다고 하면, 입지 않는 경우까지 세어서 4 * 5 * 2 가지의 경우의 수가 나온다.

하지만 적어도 하나의 옷은 입어야 하기 때문에 마지막에 1을 빼준다.

 

👶 교훈

... 생각을 하고 풀자.