[프로그래머스] 위장

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

프로그래머스

옷의 종류와 이름이 pair 로 담긴 clothes 배열이 인풋으로 들어오면, 얼마나 많은 수의 옷을 입을 수 있는 지 경우의 수를 리턴해야 한다. 당연하지만 동일 종류의 옷은 하나만 선택이 가능하다.

예를 들어, [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]  와 같이 입력이 들어왔다고 생각해보면, headgear 2개, eyewear 1개가 들어온 것이다. 이를 이용해서 착용을 할 수 있는 경우의 수는  (2+1)(1+1) - 1 = 6 - 1 = 5 와 같다.

headgear 는 총 2개 가지고 있는데, 하나도 선택하지 않을 수도 있으므로 headgear 을 선택할 수 있는 경우의 수는 2+1 = 3 개인 것이고,

마찬가지로 eyewear 는 총 1개를 가지고 있는데 하나도 선택하지 않을 수도 있으므로 eyewear 를 선택할 수 있는 경우의 수는 1+1 = 2 인 것이다.

그래서 [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]  와 같이 입력이 들어온 경우에는 2*3 = 6 의 경우의 수를 가지는데, 이 경우의 수는 단 하나도 착용하지 않은 상황 또한 포함되어 있는 것이므로 1 을 빼주어야 한다.

이를 일반화 하면 해당 문제의 답안은 (a+1)(b+1)(c+1)...(z+1) - 1 과 같다.  (a, b, c, ... , z 는 각각의 옷 종류에 대한 가지고 있는 옷의 개수를 의미한다.) 

 

여튼 위 방법을 이용하려면 각각의 종류에 대해 가지고 있는 옷의 개수를 알아내야한다. 이를 위해서 <옷의 종류, 개수> 를 pair 로 가지는 map 인 closet 을 선언하였다. 그리고 clothes 를 순회하며 해당하는 옷 종류에 대한 개수를 카운팅하였고, closet 을 순회하며 위 공식을 이용해서 최종 답안을 도출한다.

 

[C++]

#include <string>
#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <algorithm>

using namespace std;

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