c++ 프로그래머스_"위장"

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

프로그래머스

 

 

​

해시를 이용한 문제이다.

​

처음에 해시를 이용하여

각 옷 종류 별로 옷 수를 구하고,

​

옷 조합 수는

만약

상의 : 3

하의 : 2

​

라면

3*2니까,

​

종류 별로 구한 옷 개수를 부분집합 하여 곱해서 진행하였다.

​

근데 테스트케이스 1개가 시간초과가 나왔다.

하긴 30개 부분집합하면 초과 나올만 했다.

​

​

​

그래서

​

다시 위의 예를 들자면

상의 : 3

하의 : 2

이라면,

상의 * 하의

안입 * 하의

상의 * 안입

안입 * 안입

조합이 있다.

즉, ( 3 + 안입는 경우 1) x ( 2 + 안입는 경우 1) - 1 (모두 안입는 조합)

을 해주면 된다.

​

​

*

기본 수학을 잘했으면 바로 했을 것을...

하나하나 찍어가보며 찾았다..

​

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

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    
    map<string,int> mp;
    for(int i=0;i<clothes.size();i++){
        string type = clothes[i][1];
        
        mp[type]++;
    }
    
    for(auto s : mp){
        answer *= (s.second+1);
    }
    answer--;
    
    return answer;
}