[프로그래머스] 위장

문제 설명

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

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

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

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

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothes	return
[[yellow_hat, headgear], [blue_sunglasses, eyewear], [green_turban, headgear]]	5
[[crow_mask, face], [blue_sunglasses, face], [smoky_makeup, face]]	3

풀이)

경우의 수 문제이다.

옷 종류별로 unordered_map을 이용해서 분류하는 것까지는 했지만,

분류한 옷들을 어떻게 조합해서 결과를 만들어 내는지 도저히 몰라

다른 분의 코드를 보았다.

생각보다 간단한 공식이었다.

결과 = (동일 종류 1 의상 수 + 1) * (동일 종류 2 의상 수 + 1) * .... - 1

의상수에서 +1씩하는 이유는 종류 n의 의상을 안 입을 경우의 수를 추가한 것

최종적으로 -1을 하는 이유는 스파이가 아예 아무것도 안입는 경우를 제외하기 위해(문제에서 최소 한개는 입어야한다고 해서)

예로 들자면 얼굴종류가 2개, 상의가 1개, 하의가 2개 있다면

결과 = (2+1) * (1+1) * (2+1) -1 = 17

코드)

#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> cloth;
    unordered_map <string,int> ::iterator it;
    for(int i=0;i<clothes.size();i++){
        if(cloth.find(clothes[i][1]) != cloth.end()){
            cloth[clothes[i][1]]++;
        }
        else{
            cloth[clothes[i][1]] = 1;
        }
    }
    for(it = cloth.begin();it != cloth.end();it++){
        answer *= (it->second+1);  
    }
    answer -= 1;

    return answer;
}