위장

문제

문제의 시간복잡도

n의 개수가 30 이므로, $O(n^3)$ 이하의 시간복잡도에서 문제 풀이가 유효 할 것이다. 즉 시간복잡도에 대해서는 크게 생각을 안하고 넘어가도 될 것이라고 생각이 들었다.

접근법

이 문제를 처음 봤을 때의 생각은 확통에서 배우는 조합이다 라는 생각이 먼저 들었다.

그런데 각각의 옷의 종류마다 하나씩만 입을 수 있기 때문에 $nC_1$이군아 라는 생각이 들었다.

그래서 각각에 대해서 겹치는 유형의 옷들의 수를 구해서 곱하면 답이라고 생각을 했다.

그런줄로만 알았는데 몇가지 더 상황이 있었다. 먼저 선택하지 않은 경우에도 경우를 더해주어야 했다. 그리고 빨개벗은 상태는 아니기 때문에 모두가 벗겨진 상태 하나는 빼줘야 했다.

풀이

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;

    unordered_map<string,int> map;
    for(int i=0;i<clothes.size();i++)
    {
        if(map.end()==map.find(clothes[i][1]))
        {
            map.insert(make_pair(clothes[i][1],2));
        }
        else
        {
            map[clothes[i][1]]++;
        }
    }
    
    int cnt=0;
    
    for(auto& i : map)
    {
        answer = answer* (i.second);
    }
   
    return answer-1;
}