의상

문제 설명

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

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

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

코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.

 

착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다. 코니는 하루에 최소 한 개의 의상은 입습니다.

 

코니가 가진 의상들이 담긴 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

---

첫 시도

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

using namespace std;
unordered_map<string, int> answer_Map;
vector<string> type;

void DFS(unordered_map<string, vector<string>>& hash, string name, int down = 0, int right = 0)
{
    if (down >= type.size())
        return;
    string nowname = name + hash[type[down]][right];
    answer_Map[nowname] = 1;
    if(right == 0)
        for(int i = 1; i < hash[type[down]].size(); i++)
            DFS(hash, name, down, i);

    DFS(hash, nowname, down + 1);
}

int solution(vector<vector<string>> clothes) {
    int answer = 0;
    unordered_map<string, vector<string>> clothes_Map;
    for (const auto& def : clothes)
        clothes_Map[def[1]].emplace_back(def[0]);
    for (const auto& def : clothes_Map)
        type.emplace_back(def.first);

    for(auto& def : type)
    DFS(clothes_Map, string(""));

    for (auto& def : clothes_Map)
        for (auto& def1 : def.second)
            cout << def.first << ", " << def1 << endl;
    return answer_Map.size();
}

실패

 

재귀로 풀려고 시도했음, 중복값을 처리하려면, 먼저 전부다 순회하면서 그냥 값을 중복제외하고, 나머지 사이즈를 가져오면 된다고 생각함.

---

두 번째 시도

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
    
int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map<string, int> counts;
    for (const auto& item : clothes) 
        counts[item[1]]++;
    for (const auto& pair : counts)
        answer *= (pair.second + 1);

    return answer - 1;
}

성공

 

조금 더 프로그래머 스럽게 생각해보기로 했음.

과정이 필요한가? 그냥 중복되지 않은 값이 얼마나 있는지 확인하기만 하면 되는데?

 

모든 객체를 분류해서 값을 정렬함, 예를들어 모자 2개 코트 3개 바지 1개 라고 가정하면 해당 데이터를 전부 정렬해줌.

 

그리고, 모든 값들을 순회하면서 정답에 값에 1을 더한값을 곱해주면 됨.

 

그러면, 모자 2개 코트 3개 바지 1개 일때, 각 값에 따른 중복되지 않은 경우의 수가 나타나게됨

아무것도 없을때의 초깃값 한개를 빼주면 결과값이다.

과정따위는 필요없는 차가운 프로그래밍...