[프로그래머스] 의상

문제

---

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

프로그래머스

 

문제 분석

---

[제한사항]

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

 

종류마다 옷을 하나씩 착용할 수 있고 옷을 하나도 착용하지 않을 수는 없다.

착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산한다.

 

예시)

모자 : hat_1, hat_2

바지 : pants

 

정답) (hat_1), (hat_2), (pants), (hat_1, pants), (hat_2, pants) => 5개

 

문제 접근

---

처음에는 그냥 완전 탐색을 통해 가능한 모든 경우를 전부 체크해서 문제를 풀려고 했다.

=> 크기 30 정도면 작다고 생각했고 충분히 풀 수 있겠다고 판단했다. 

=> 하지만 1번 테스트 케이스에서 계속 시간초가가 나와 30으로 나올 수 있는 경우의 수를 계산했다.

 

30 가지 옷 중 1개 만 선택하는 경우 + 2개 선택 하는 경우 + . . . + 30개 선택 하는 경우 를 계산해보면

30 + 30*29 + 30*29*28 + . . . + 30! = 1,073,741,823 이 나온다.

 

30 정도면 크기가 작다고 생각했는데 전혀 아니였다...

 

 

그래서 경우의 수를 계산해서 문제를 풀려고 접근하였다.

 

모자 : 2개

바지 : 1개 

 

모자 자리에는 없는 경우, 1번 모자 쓴 경우, 2번 모자 쓴 경우 이렇게 3가지의 경우가 나온다.

바지 자리에는 없는 경우, 1번 바지를 입은 경우 2가지가 나온다.

 

이를 계산하면 3 X 2 - 1 = 5 가 나온다. 

(없는 경우, 없는 경우) 는 제외해야 하기 때문에 마지막에 1을 빼주어야 한다.

 

위 식을 코드로 구현만 해주면 풀 수 있다.

 

Map<String, Integer> 자료형에 부위별 옷의 개수를 카운트하고 위의 식을 활용해 문제를 해결하였다.

 

코드

---

(실패) - 완전탐색

import java.util.*;

class Solution {
    static int answer = 0;
    public int solution(String[][] clothes) {
        
        Map<String, Boolean> visited = new HashMap<>();
        Set<String> set = new HashSet<>();
        for(String[] clothe : clothes){
            set.add(clothe[1]);
        }
        int max = set.size();
        dfs(0, clothes, visited, max);
        return answer;
    }
    
    public void dfs(int start, String[][] clothes, Map<String, Boolean> visited, int max){
        if(visited.size() >= max){
            return;
        }
        
        for(int i=start; i<clothes.length; i++){
            if(!visited.containsKey(clothes[i][1])){
                answer++;
                visited.put(clothes[i][1], true);
                dfs(i+1, clothes, visited, max);
                visited.remove(clothes[i][1]);
            }
        }
    }
}

 

(성공)

import java.util.*;

class Solution {
    static int answer = 1;
    public int solution(String[][] clothes) {
        
        Map<String, Integer> clothesCnt = new HashMap<>();
        
        for(String[] arr : clothes){
            clothesCnt.putIfAbsent(arr[1], 0);
            clothesCnt.put(arr[1], clothesCnt.get(arr[1]) + 1);
        }
   
        for(String key : clothesCnt.keySet()){
            answer *= (clothesCnt.get(key) + 1);
        }
        return answer - 1;
    }
}