[프로그래머스 lv2] 위장 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

아이템의 종류와 이름이 주어졌을 떄, 가능한 모든 조합을 구하는 문제이다.

같은 종류의 아이템은 한번에 하나만 매치할 수 있고, 0개의 아이템을 매치하는 것을 제외하고는 모든 경우가 가능하다.

 

결론부터 말하자면, a1 종류의 아이템이 a2개, b1 종류의 아이템이 b2개, c1 종류의 아이템이 c2개 ... 있을 때,

가능한 모든 경우의 수는 (a2+1) * (b2+1) * (c2+1) * ... -1 이다. 

 

한 종류의 아이템에 대하여, 한번에 하나만 매치하거나 아에 매치하지 않을 수 있으므로 (아이템의 개수 + 0이라는 경우의 수 1)이 가능하다. 이를 모두 곱해주면 가능한 모든 경우의 수가 나오는데, 문제에서 모든 아이템을 매치하지 않는 경우는 제외하라고 했으므로 마지막에 1을 뺴주면 정답이다.

 

 

코드 

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(vector<vector<string>> clothes) {
    
    unordered_map<string, vector<string>> mp;
    
    for (auto v : clothes)
        mp[v[1]].push_back(v[0]);
    
    int ret = 1;
    for (auto [k, v] : mp)
        ret *= (v.size()+1);
    return ret-1;
}