Post

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

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

문제 링크


1. 아이디어

종류마다 최대 한 가지만 입을 수 있고 하루에 한 벌 이상은 입을 때 서로 다른 조합의 수를 구하는 문제다. 어떤 종류의 의상이 $k$벌이면 그 종류에서는 $k$벌 중 하나를 입거나 아무것도 입지 않는 $k + 1$가지 선택이 있고, 종류마다 선택이 서로 독립이므로 모든 종류의 $k + 1$을 곱하면 종류별 선택을 모두 정한 경우의 수가 된다. 이 곱에는 모든 종류에서 아무것도 입지 않는 경우가 한 번 들어 있는데 하루에 한 벌은 입어야 하므로 1을 뺀다. 필요한 것은 의상 이름이 아니라 종류별 벌 수뿐이다.


2. 코드

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;

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

        int ans = 1;
        for (int v : cnt.values()) {
            ans *= v + 1;
        }

        return ans - 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

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

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

    return ans - 1;
}
1
2
3
4
5
6
7
import math
from collections import Counter


def solution(clothes):
    cnt = Counter(kind for _, kind in clothes)
    return math.prod(v + 1 for v in cnt.values()) - 1

This post is licensed under CC BY 4.0 by the author.