위장

문제 링크 => 코딩테스트 연습 - 위장 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 위장

---

조합 문제이다.

 

옷 종류 a, b, c, ..., z 가 있다고 가정하자.

 

a 의 갯수를 cntA, b 의 갯수를 cntB, ... ,  z 의 갯수를 cntZ 라고 할 때, 다음과 같은 식을 통해 경우의 수를 구할 수 있다.

 

answer = (cntA + 1) * (cntB + 1) * ... * (cntZ + 1) - 1

 

여기서 + 1 을 하여 곱한 이유는 해당 옷을 입지 않을 수 있으며 마지막에 - 1 을 한 이유는 모든 옷을 입지 않은 경우는 제외해야 하기 때문이다.

 

풀이 Code

 

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    
    vector<string> type;
    map<string, int> m;
    
    for(int i=0; i<clothes.size(); i++){
        if(!m[clothes[i][1]]){
            type.push_back(clothes[i][1]);
            m[clothes[i][1]]++;
        }
        else m[clothes[i][1]]++;
    }
    
    for(int i=0; i<type.size(); i++){
        answer *= (m[type[i]] + 1);    
    }
    
    return answer - 1;
}