위장

코드

[ 내가 푼 코드 ]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
/* 조합을 구하는 것! */
int combination (int n, int r){
    if(n == r || r == 0)
        return 1;
    else
        return combination(n-1,r-1) + combination(n-1, r);
}

int solution(vector<vector<string>> clothes) {
    int answer = 1, idx;
    vector<int> num;
    vector<string> str;
    // 종류별로 카운트 세기
    for(int i=0;i<clothes.size();i++)
    {
        auto result = find(str.begin(), str.end(), clothes[i][1]);
        if(result != str.end()){
            idx = find(str.begin(), str.end(), clothes[i][1]) - str.begin();
            num[idx]++;
        }else{
            str.push_back(clothes[i][1]);
            num.push_back(1);
        }
    }
    // 조합을 이용해 개수 구하기
    for(int i=0;i<num.size();i++)
    {
        answer *= combination(num[i]+1,1);
    } 
    return answer-1;
}

• 풀이의 원리
  1) 각 옷 종류들이 몇개씩 있는지 개수를 카운트 해서 vector에 넣는다
  2) 각 종류마다 선택지는 총 (개수+1)개가 있다 --> 선택하지 않는것도 포함
  3) 조합(nCr)을 이용해서 개수를 구한 뒤 마지막에 1을 뺀다 (아무것도 선택하지 않는 경우)

---

[ 최적의 코드 ] - map사용!

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1, idx;
    map<string, int> str;
    // 종류별로 카운트 세기
    for(int i=0;i<clothes.size();i++)
    {
        str[clothes[i][1]]++;
    }

    for(auto it = str.begin();it != str.end();it++)
    {
        answer *= it->second+1;
    }
    return answer-1;
}

• map자료형을 쓰면 key값으로 값을 저장하고 바로 개수를 셀 수 있음! (좋다~)
• 어차피 조합을 쓸 때 nC1만 쓰니까 그냥 조합을 안만들고 곱해도 가능함!