[프로그래머스] 위장(JAVA) / 해시 Level2

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

프로그래머스

---

풀이

경우의 수 성질을 이용하면 간단하게 해결될 문제였는데... 삽질을 엄청 했다.
쉽게 풀 수 있는 문제를 순열까지 구현해서 돌려가며 코딩했는데... 케이스 하나에서 시간초과가 나서 실패했다.

 

틀린 코드

5개 종류의 옷이 입력으로 주어졌다고 했을 때 1개 종류만 입을 경우, 2개 종류만 입을 경우 ... 등을 구하고 각 경우마다 해당 종류의 옷이 몇개 인지 확인해서 경우의 수를 구했다. 시간을 줄이겠다고 해쉬맵까지 섞어서 순열을 구했으나... 시간초과가 났다.
어쩌면 문제의 출력이 입을 수 있는 매칭 가지 수가 아니라 매칭한 옷의 내용을 출력하는 거였다면 이렇게 푸는게 맞았을 수도 있겠다. 그러나 본 문제는 가지 수만 구하면 되는 문제기 때문에... 훨씬 간단하게 짤 수 있다.

import java.util.HashMap;
import java.util.LinkedHashMap;

class Solution {
    int[] combi;
    String[] type;
    int n;
    int answer = 0;
    HashMap<String, Integer> hp = new HashMap<>();

    public void dfs(int L, int s, int m) {
        if (L == m) {
            int tmp = 1;
            for (int i = 0; i < m; i++) {
                tmp *= hp.get(type[combi[i]]);
            }
            answer += tmp;
            return;
        }
        for (int i = s; i < n; i++) {
            combi[L] = i;
            dfs(L + 1, i + 1, m);
        }
    }

    public int solution(String[][] clothes) {

        for (String[] c : clothes) {
            hp.put(c[1], hp.getOrDefault(c[1], 0) + 1);
        }
        n = hp.size();
        combi = new int[n];
        type = new String[n];

        int index = 0;
        for (String s : hp.keySet()) {
            type[index] = s;
            index++;
        }
        for (int i = 1; i <= n; i++) {
            dfs(0, 0, i);
        }
        return answer;
    }
}

 

 

맞은 코드

위와 같은 경우, 각 종류마다 선택할 수 있는 선택권은 종류를 선택하지 않는 경우를 1을 더한 (이름 수+1) 이다
다시말해, (동그란 안경을 선택한 경우+검정 선글라스를 선택한 경우+선택하지 않은 경우) * (파란색 티셔츠를 선택한 경우+선택하지 않은 경우)*(청바지를 선택한 경우+선택하지 않은 경우)*(긴 코트를 선택한 경우+선택하지 않은 경우) 이다.

이 때, 선택하지 않은 경우+선택하지 않은 경우+선택하지 않은 경우+선택하지 않은 경우 = 아무것도 입지않음 의 경우가 생기므로 마지막에 1을 빼주어야한다.

import java.util.HashMap;

class Solution {

    public int solution(String[][] clothes) {

        int answer = 1;
        HashMap<String, Integer> hp = new HashMap<>();
        for (String[] c : clothes) {
            hp.put(c[1], hp.getOrDefault(c[1], 0) + 1);
        }
        for (Integer value : hp.values()) {
            answer *= (value + 1);
        }

        return answer-1;
    }
}

 

 

+ 이 외 코드

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())))
                .values()
                .stream()
                .collect(reducing(1L, (x, y) -> x * (y + 1))).intValue() - 1;
    }
}

스트림을 엄청 능숙하게 쓰신 분의 코드가 있어서 참고용으로 살펴보았으나... 아직 내가 스트림에 대한 이해가 부족해서 완전히 이해가 되진 않는다. 다음에 다시 살펴보는 것으로...