[Programmers] #42578 - 의상 [Java][C++][Python]

문제 링크

---

1. 아이디어

의상 목록 clothes가 주어질 때, 종류별로 최대 1가지씩만 착용하면서 최소 한 개는 입어야 하는 조합의 수를 구하면 되는 문제다. 먼저 해시맵으로 종류별 의상 개수를 세줬다. 각 종류마다 “그 종류를 안 입기”와 “그 종류의 의상 중 하나를 입기” 중 하나를 고를 수 있으므로, 종류별 경우의 수는 (해당 종류 의상 개수 + 1)가지다. 이를 모든 종류에 대해 곱하면 아무것도 안 입는 경우까지 포함한 전체 조합 수가 나오므로, 마지막에 1을 빼서 최소 한 개는 입는 경우만 남겼다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = clothes의 길이)

---

3. 코드

풀이 [Java][C++][Python]

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 ans = 1;
        for (int v : map.values()) {
            ans *= v + 1;
        }

        return ans - 1;
    }
}

#include <bits/stdc++.h>
using namespace std;

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

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

    return ans - 1;
}

import math
from collections import Counter


def solution(clothes):
    cnt = Counter(t for _, t in clothes)

    return math.prod(v + 1 for v in cnt.values()) - 1

---