[프로그래머스/C++] 의상

✅ LV.2

✏️ 1차 솔루션

1. 옷 종류별로 개수 count를 위해 {옷 종류, 개수} 로 map 에 저장
2. 옷을 입는 모든 경우의 수를 조합으로 구하기
3. 입을 종류의 옷의 경우의 수 count 해서 최종 answer 만들기

🚨 1차 trouble

시간초과
조합을 만들기 위해서 vector나 메모리 낭비가 심해서 맞는 방법인지 모르겠음

✏️ 최종 솔루션

옷을 안 입는 경우도 하나의 옵션으로 생각한다면 모든 옷을 무조건 한번씩은 입는 것으로 간주하여 각 종류의 옷 개수+1 을 곱해주고 모든 옷을 입지 않는 경우의 수 1만 빼주면 계산 가능

📌 self feedback

종류는 구분해야하지만 어떤 옷을 입는지는 신경 쓸 필요가 없기 때문에 옷을 안 입는 것을 옵션으로 간주해서 알고리즘을 간단하게 만드는 것이 관건

✏️ 최종 code

#include <string>
#include <vector>
#include <map>

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 key=clothes[i][1];
        mp[key]++;
    }
    
    for(auto it:mp) {
        string key=it.first;
        mp[key]++;
        answer*=mp[key];
    }
   
    
    return answer-1;
}