프로그래머스 - 의상 (해시)

문제 설명

코니는 매일 다른 옷을 조합하여 입는 것을 좋아합니다.

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

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

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다.
  (예: 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없음)
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 의상을 추가로 더 착용하면 서로 다른 방법으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

clothes 배열이 주어질 때, 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성하세요.

---

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류] 로 이루어져 있습니다.
• 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름의 의상은 존재하지 않습니다.
• 모든 원소는 길이가 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

 

---

구하는 것 : 모든(각 옷의 종류의 개수 + 1)의 곱 - 1
옷의 종류의 개수를 구헤야 한다.
종류 : 갯수의 자료 형태가 어울리겠다 -> Map을 쓰겠다.

 

알고리즘 코드

import java.util.HashMap;

class Solution {
    public int solution(String[][] clothes) {
        HashMap<String, Integer> map = new HashMap<>();
        
        for(String[] clothe : clothes) {
            // clothe = {이름, 타입}
            String key = clothe[1]; // 이름을 key로 지정
            
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        
        int answer = 1;
        
        for(Integer value : map.values()) {
            answer *= (value + 1);
        }
        
        return answer - 1;
    }
}

 

 

시간 복잡도 분석

의상 배열을 한 번 순회하면서 HashMap에 종류별 개수를 세고, 의상 종류의 수(k) 만큼 반복한다. 

따라서 전체적인 시간 복잡도를 구하면 O(n + k) ≈ O(n)이다.