[프로그래머스 - 해싱] 위장 (Java)

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

프로그래머스

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

 

종류이름

얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothes	return
[[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]	5
[[crow_mask, face], [blue_sunglasses, face], [smoky_makeup, face]]	3

 

입출력 예 설명

예제 #1
headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat

2. blue_sunglasses

3. green_turban

4. yellow_hat + blue_sunglasses

5. green_turban + blue_sunglasses

 

예제 #2
face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask

2. blue_sunglasses

3. smoky_makeup

 

 

접근 방식

해싱 문제로 분류되어 있었지만 개인적으로는 경우의 수를 조합하는 쪽이 비중이 큰 문제였던 것 같다.(이 마저도 아닌 걸 마지막에 알아버리긴 했지만..)

 

우선 HashMap을 이용해 key-옷의 종류, value-갯수를 담았다.

(한가지 새로 알게된 코드! 해쉬맵의 getOrDefault({key}, default) 메소드를 사용하면 if-else문 사용 없이 디폴트값과 get으로 값을 얻어내는 코드를 한줄로 작성할 수 있었다.)

 

그 다음 조합이 되는 경우의 수를 구하는 코드를 구현해야했다.

1개 선택하는 경우의 수

2개 선택하는 경우의 수

...

n개 선택하는 경우의 수를 각각 구해 answer에 더하는 방식으로 구현하고자 했고,

백트래킹 방법으로 구현을 했다.

 

결론은 답은 나오지만 시간 복잡도 측면에서 효율적이지 못했다. (첫번째 테스트 케이스를 시간초과로 통과하지 못했다.)

그래서 다른 분들의 코드를 참고했더니 너무나도 간단하게 경우의 수를 구하는 식이 존재했다.

알고리즘이 문제가 아니라 수학적 지식이 모자라 자력으로 풀지 못한 문제였다...

 

소스 코드

public class Camouflage {

    public int solution(String[][] clothes) {
        int answer = 1;
        Map<String, Integer> hashMap = new HashMap<>();

        for (String[] cloth : clothes) {
            hashMap.put(cloth[1], hashMap.getOrDefault(cloth[1], 0) + 1);
        }

        for (int value : hashMap.values()) {
            // 옷 가지수 + 안입는 경우
            answer *= (value + 1);
        }

        // 옷을 하나도 안입는 경우는 없으니까 빼줌
        answer--;

        return answer;
    }

// 백트래킹으로 푼 경우 (시간 초과)
    public int solution(String[][] clothes) {
        Map<String, Integer> hashMap = new HashMap<>();

        for (String[] cloth : clothes) {
            hashMap.put(cloth[1], hashMap.getOrDefault(cloth[1], 0) + 1);
        }

        for (int i = 1; i <= hashMap.size(); i++) {
            if (i == 1) {
                answer += clothes.length;
                continue;
            }

            boolean[] visited = new boolean[hashMap.size()];
            combination(hashMap.values().toArray(new Integer[0]), visited, i, 0, 0);
        }

        return answer;
    }

    private void combination(Integer[] arr, boolean[] visited, int count, int now, int index) {
        if (count == now) {
            int result = 1;

            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    result *= arr[i];
                }
            }

            answer += result;
        }

        for (int i = index; i < visited.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                combination(arr, visited, count, now + 1, i + 1);
                visited[i] = false;
            }
        }
    }
}