위장

https://programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

 

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    unordered_map<string, vector<string>> clothesHashMap;
    
    // 먼저 분류한다.
    for (const vector<string>& c : clothes) {
        const auto name = c[0];
        const auto category = c[1];
        const auto f = clothesHashMap.find(category);
        if (f != clothesHashMap.end()) {
            f->second.push_back(name.c_str());
        }
        else {
            vector<string> names;
            names.emplace_back(name.c_str());
            clothesHashMap.insert(make_pair(category.c_str(), names));
        }
    }

    // n개의 선택지중에 순서에 상관없이 하나를 선택하는 문제이므로 n Combination 1 , nC1을 구한다.
    // 그런데 안입는 경우도 있으므로 n+1 Combination 1 
    int mulCombination = 1;
    for (auto c : clothesHashMap) {
        mulCombination *= (c.second.size() + 1);
    }

    // 아무것도 안입는건 빼준다
    return mulCombination - 1;
}

 

 

분류하는 코드는 생각해보니 소팅하거나 하면 좀 더 간단하게 할 수 있을거 같다.

문제의 핵심은 고1 때 배운 콤비네이션을 아냐 모르냐 인 듯