해시 - 위장

C++

해시 - 위장

문제

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

문제 출처

접근 방법

고등학교 수학시간때 배웠던 경우의 수만 떠올려야하는 문제이다.
스파이는 n개 종류의 옷을 매일 다른 조합으로 바꾸어 입어야하므로 모든 종류의 옷의 개수와 그 옷을 입지 않았을 때의 경우 + 1을 더하여 곱해준다.
즉, 안경 2개 - 상의 1개 - 하의 1개 라면
(2 + 1) * (1 + 1) * (1 + 1) = 12개이다.
여기서, 최소한 하나의 옷은 입어야 하므로 모두 안뽑는 경우를 하나 빼주면,
12 - 1 = 11 즉 11개의 경우가 나온다.

구현

unordered_map<string,int>

코드

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map<string, int> spy;
    for (int i = 0; i < clothes.size(); i++) {
        string key = clothes.at(i).at(1);       //옷의 종류
        if (spy.count(key) == 0){               //만약 해당하는 종류가 없으면
            spy.insert(make_pair(key, 1));      
        }
        else {                                  //있으면
            int temp = spy.find(key)->second;   
            temp++;                             //개수를 늘려준다.
            spy[key] = temp;
        }
    }
    unordered_map<string, int>::iterator it;    //map을 순환 시킨다.
    for (it = spy.begin(); it != spy.end(); it++) {
        answer *= (it->second + 1);
    }
    answer--;                                   //옷을 안 입엇을 경우
    return answer;
}

후기 및 개선할 점

처음에 별 생각없이 모든 옷의 종류를 map에 넣으려 하였고,
또한 고등학교 때의 기억을 잊어버린지 오래라 공식을 생각하지 못하였다.