[프로그래머스] 42578번 - 의상 [Java][C++]

문제 링크

---

문제 설명

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

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

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

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

코니가 가진 의상들이 담긴 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

---

1. 문제 풀이

의상의 종류를 키로 해당 종류의 의상의 수를 값으로 갖는 해시맵을 활용하면 해결할 수 있다. 해당 종류의 의상의 수가 $N$ 가지일 때 해당 종류의 의상을 입는 경우의 수는 $N$ 가지이며 안 입는 경우 $1$ 가지가 있어 각 종류마다 해당 종류의 수 $+1$ 가지 경우의 수가 생긴다. 각각의 종류마다 독립 시행이므로 곱 연산이 전체 경우의 수가 되며 의상을 아예 안입는 경우는 없으므로 $-1$ 을 해주면 코니가 입을 수 있는 모든 조합의 수를 찾을 수 있다.

---

2. 코드

1. 해시를 사용한 집합과 맵 [Java]

HashMap 에 저장 후 values 메서드로 값에 대해서만 순회하는 방식으로 해결했다.

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        Map<String, Integer> map = new HashMap<>();
        for (String[] c : clothes) {
            map.put(c[1], map.getOrDefault(c[1], 0) + 1);
        }

        int answer = 1;
        for (int n : map.values()) {
            answer *= n + 1;
        }

        return answer - 1;
    }
}

2. 해시를 사용한 집합과 맵 [C++]

#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, int> mp;
    for (auto& v : clothes) {
        mp[v[1]]++;
    }

    int ans = 1;
    for (auto& [key, value] : mp) {
        ans *= value + 1;
    }

    return ans - 1;
}

---

3. 풀이 정보

1. 해시를 사용한 집합과 맵 [Java]

정확성 테스트
테스트 1 〉 통과 (0.07ms, 87.1MB)
테스트 2 〉 통과 (0.06ms, 76.4MB)
테스트 3 〉 통과 (0.12ms, 80.4MB)
테스트 4 〉 통과 (0.14ms, 87.7MB)
테스트 5 〉 통과 (0.04ms, 89.6MB)
테스트 6 〉 통과 (0.05ms, 80.1MB)
테스트 7 〉 통과 (0.12ms, 88.2MB)
테스트 8 〉 통과 (0.09ms, 69.2MB)
테스트 9 〉 통과 (0.04ms, 70.2MB)
테스트 10 〉 통과 (0.04ms, 86MB)
테스트 11 〉 통과 (0.06ms, 76.6MB)
테스트 12 〉 통과 (0.12ms, 81.8MB)
테스트 13 〉 통과 (0.08ms, 84.8MB)
테스트 14 〉 통과 (0.04ms, 76.2MB)
테스트 15 〉 통과 (0.04ms, 75.4MB)
테스트 16 〉 통과 (0.05ms, 69.5MB)
테스트 17 〉 통과 (0.07ms, 75.4MB)
테스트 18 〉 통과 (0.07ms, 89.2MB)
테스트 19 〉 통과 (0.04ms, 74.8MB)
테스트 20 〉 통과 (0.06ms, 71.8MB)
테스트 21 〉 통과 (0.04ms, 81.1MB)
테스트 22 〉 통과 (0.04ms, 76MB)
테스트 23 〉 통과 (0.05ms, 90.3MB)
테스트 24 〉 통과 (0.07ms, 82.8MB)
테스트 25 〉 통과 (0.05ms, 77.5MB)
테스트 26 〉 통과 (0.09ms, 94.2MB)
테스트 27 〉 통과 (0.04ms, 81.7MB)
테스트 28 〉 통과 (0.06ms, 83.8MB)

2. 해시를 사용한 집합과 맵 [C++]

정확성 테스트
테스트 1 〉 통과 (0.02ms, 4.09MB)
테스트 2 〉 통과 (0.01ms, 4.19MB)
테스트 3 〉 통과 (0.01ms, 4.11MB)
테스트 4 〉 통과 (0.02ms, 4.19MB)
테스트 5 〉 통과 (0.01ms, 4.12MB)
테스트 6 〉 통과 (0.01ms, 4.19MB)
테스트 7 〉 통과 (0.02ms, 4.18MB)
테스트 8 〉 통과 (0.01ms, 4.18MB)
테스트 9 〉 통과 (0.01ms, 3.62MB)
테스트 10 〉 통과 (0.01ms, 4.12MB)
테스트 11 〉 통과 (0.01ms, 4.19MB)
테스트 12 〉 통과 (0.02ms, 4.18MB)
테스트 13 〉 통과 (0.02ms, 3.66MB)
테스트 14 〉 통과 (0.01ms, 4.13MB)
테스트 15 〉 통과 (0.01ms, 3.62MB)
테스트 16 〉 통과 (0.01ms, 4.13MB)
테스트 17 〉 통과 (0.01ms, 4.12MB)
테스트 18 〉 통과 (0.01ms, 4.19MB)
테스트 19 〉 통과 (0.01ms, 4.13MB)
테스트 20 〉 통과 (0.01ms, 4.12MB)
테스트 21 〉 통과 (0.01ms, 4.12MB)
테스트 22 〉 통과 (0.01ms, 4.2MB)
테스트 23 〉 통과 (0.01ms, 3.67MB)
테스트 24 〉 통과 (0.01ms, 4.2MB)
테스트 25 〉 통과 (0.01ms, 4.18MB)
테스트 26 〉 통과 (0.02ms, 4.12MB)
테스트 27 〉 통과 (0.01ms, 4.16MB)
테스트 28 〉 통과 (0.01ms, 4.13MB)

---