[프로그래머스] 위장 (C++)

풀이

핵심은 선택하지 않는 경우를 고려해야 한다.

입출력 예시를 보면

headgear에는 yellowhat, green_turban 2개

eyewear에는 bluesunglasses 1개

위장을 하려면 headgear만 쓰거나 eyewear만 쓰거나 혹은 headgear, eyewear 같이 쓰는 경우다.

그런데 headgear만 쓴다는 것은 eyewear는 쓰지 않는다는 것을 의미하니 다음과 같이 생각할 수 있다.

[headgear, x]

[eyewear, x]

[headgear, eyewear]

위를 고려하면,

heargear는 기존 2개에 +1(선택하지 않는 경우) => 3개

eyewear는 기존 1개에 +1(선택하지 않는 경우) => 2개

두 옷을 골라서 조합하면

3 x 2 = 6가지가 나오게 되는데, 위장은 최소 한 개의 옷은 입어야 하므로 마지막의 경우에 [x, x] 는 빼줘야 한다.

따라서 6 - 1 = 5가지가 나오게 된다.

 

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

int solution(vector<vector<string>> clothes) {
    map<string, int> m;
    for(auto v : clothes) {
        m[v[1]]++;
    }
    
    int answer = 1;
    for(auto iter = m.begin(); iter != m.end(); iter++) {
        answer *= (iter->second + 1);
    }
    return answer - 1;
}