위장 (프로그래머스)

옷을 입는 경우의 수를 도출하는데에 애를 많이 먹은 문제였다;;

 

우선 해시를 이용하여 해당 종류의 맞는 옷의 갯수를 컨테이너에 기록한다. (key값은 옷의 종류 이름, value값은 그 종류의 옷 개수) 옷의 이름은 이 문제를 해결하는데에 전혀 필요가 없다.

 

옷의 종류별 갯수를 알았으니 이제 이 스파이가 위장할 옷을 입는 경우의 수를 구할 차례이다. 예를들어 얼굴 종류의 옷 5개와 하의 종류의 옷 4개가 있다고 하자. 만약 이 옷을 두가지 모두 입어야 한다면 5 * 4 = 20가지 조합이 나온다. 하지만 옷을 안입는 경우도 있으므로 안입은 경우를 추가해줘야 한다. 그래서 조합 수 는 (5 + 1) * (4 + 1) = 30가지이다. 

 

하지만 30은 정답이 아니다! 위 조건에서 "스파이는 하루에 최소 한 개의 의상은 입습니다." 부분을 숙지해야 한다. 이 말인 즉슨, 아무것도 안입는 경우는 빼야한다는 것이다. 그래서 최종적인 경우의 수는 30 - 1 = 29가지이다. 

 

코드는 다음과 같다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<vector<string>> clothes) 
{
    int answer = 1;
    
    unordered_map<string, int> d;
    for(const auto iter : clothes) d[iter[1]]++;
    for(const auto iter : d) answer *= (iter.second + 1);
    
    return answer - 1;
}