프로그래머스_위장(해시)

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

코딩테스트 연습 - 위장 | 프로그래머스

해당 문제는 해시 문제로 STL 라이브러리의 map을 통해 문제를 해결하였다.

의상 분류에 맞게 의상 개수를 증가 시키고 해당 분류의 조합으로 구성할 수 있는 의상 개수를 구하면 된다.

이 때 0(안입음) ~ 개수 중에서 몇 번 의상을 입을 것인 지를 고려하면 된다.

즉, 해당 의상 종류의 개수 +1 * 해당 의상 종류의 개수 +1 * ...

이런식으로 끝까지 곱한다음 0000....00 의 아무것도 입지 않은 경우의 수 1개만 빼주면 된다.

#include <string>
#include <vector>
#include <map>
using namespace std;

int solution(vector<vector<string>> clothes) {
    map<string, int> mp;
    
    // 입력하기
    for(int i=0;i<clothes.size();i++){
        auto search = mp.find(clothes[i][1]); // 찾기
        if(search != mp.end())
            search->second +=1;
        else
            mp.insert(pair<string,int>(clothes[i][1],1));
    }
    
    // 1개 일 경우 예외 처리
    if(mp.size()==1)
        for(auto search : mp)
            return search.second;
    
    // 그 외 조합하기
    int answer = 1;
    for(auto search : mp)
        answer *= (search.second+1); // 각 조합 0~해당개수
    answer--; // 모두 입지 않았을 경우 제외
    return answer;
}