[프로그래머스] 위장 - Hash

SWIFT로 Hash 문제에 대해서는 풀어봤었습니다.

하지만 Java로는 Hash 자료구조 문제를 풀어본 적이 없어서 프로그래머스의 문제를 풀어보았습니다.

 

프로그래머스 위장 문제

코딩테스트 연습 - 위장

 

 

문제는

스파이가 매일 다른 옷의 조합을 입어야 하는데,
처음 clothes 이차원 배열의 형태로 (옷의 종류, 옷의 이름)이 주어지고 이를 이용해서 만들 수 있는 조합의 수를 찾는 것입니다.
단, 스파이는 꼭 한 종류의 옷을 하나는 입어야합니다.
즉, 하나도 안 입는 경우는 존재하지 않습니다.

 

Hash문제이기 때문에, 우선 문제를 해결하기 위해 (key, value)의 형태로 HashMap을 만들어야합니다.

HashMap<String, Integer> clothes_set = new HashMap<>();

for (int i = 0; i < clothes.length; i++) {
    if (clothes_set.get(clothes[i][1]) == null) {
        clothes_set.put(clothes[i][1], 1);
    } else {
        clothes_set.put(clothes[i][1], clothes_set.get(clothes[i][1]) + 1);
    }
}

다음과 같이 초기화하였습니다.

 

그런데 여기서 왜 Integer을 활용하여 초기화하였을까요...?

저도 처음에는 조합을 만들려고 하였으나 생각해보니 조합의 수만 구하기 때문에, 확률과 통계 때 배웠던 조합의 수를 구하는 식을 적용하기 위해서 였습니다.

 

만약 3가지의 종류의 옷이 있는데 각각 (1, 5, 4)개의 옷을 가지고 있으면,

조합의 수는 (1 * 5 * 4)가 됩니다.

 

그렇다면 이번 문제에서는 어떻게 적용할까요?

안 입는 경우도 존재하기 때문에, 각 종류별로 +1을 하였습니다.

그리고 마지막으로 전부 안입는 경우는 안된다고 분명히 조건에 명시되어 있죠⁉️ 

이를 위해, -1을 해주었습니다.

int answer = 1;

for (String key : clothes_set.keySet()) {
    answer *= clothes_set.get(key) + 1;
}

answer -= 1;

각 종류의 key에 해당하는 옷의 수를 가져오고,

+1을 해서 답에 곱해주었습니다. 그리고 마지막으로 -1을 해주면 답을 알 수 있습니다.

 

전체 소스코드는

import java.util.HashMap;
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        HashMap<String, Integer> clothes_set = new HashMap<>();

        for (int i = 0; i < clothes.length; i++) {
            if (clothes_set.get(clothes[i][1]) == null) {
                clothes_set.put(clothes[i][1], 1);
            } else {
                clothes_set.put(clothes[i][1], clothes_set.get(clothes[i][1]) + 1);
            }
        }

        for (String key : clothes_set.keySet()) {
            answer *= clothes_set.get(key) + 1;
        }
        
        return answer - 1;
    }
}