[프로그래머스] 의상 (해시)

의상

매일 다른 코디 조합

clothes 행 : [의상 이름, 의상 종류] 문자열
의상 수 1~30개 이하
의상 이름 중복 x
문자열 길이 1~20 이하, 소문자, _

예제
노란모자, 헤드기어
선글라스, 눈 옷
초록터반 헤드기어

 

생각 및 이해

카테고리 별로 숫자만 중요할 듯하다

생각 1 )
if [2,1]
한 카테고리만 3 (총 개수)
두 카테고리 2*1 (각 개수의 곱)

if [3]
한 카테고리만

if [3,9, 19, 2]
한 카테고리 = 총합 nC1
두 카테고리 = 둘 씩 곱? (3*9 + 3*19 + 3*2 + 9*19 + 9*2 + 19 * 2) a
세 카테고리 = 셋 씩 -----------------비효율적인 것 같다

 

생각 2 )

if 한 카테고리에 의상 종류 = 4
then 5가지 경우의 수 (각 의상 + 아무것도 선택하지 않음)

if [ 3, 9, 19, 2]
then (3+1)*(9+1)*(19+1)*(2+1)

But, 모든 카테고리에서 아무것도 선택하지 않는 경우 빼기

 

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map<string, int> myMap;
    
    for (int i = 0; i < clothes.size(); i++) {
        myMap[clothes[i][1]]++;
    }
    
    for (auto& pair : myMap) {
        answer *= pair.second + 1;
    }
    
    return answer - 1;
}

비슷한 원리 ) 

약수의 개수 구하기 ( - 1)