[ 프로그래머스 위장 (Lv2) ] (C++)

프로그래머스의 위장(Lv2) 문제이다.

[ 문제풀이 ]

1) 먼저 본인은 의상의 종류에 따라서 매개변수로 호출되는 clothes들을 자료구조 해쉬를 통해서 관리해 주었다.

   매개변수로 호출되는 clothes 벡터를 보게되면, "의상이름 , 의상의 종류" 로 저장된 채로 매개변수로 넘어오게 되는데

   본인은 이 중에서 '의상의 종류'로 해싱해 주었다. 키 값으로는 간단하게 의상의 종류의 가장 첫번째 알파벳으로

   설정해 주었다.

   예를 들어서 "A headgear" , "B headgear" , "C face" 이렇게 왔다고 가정해보자.

   A headgear를 보고 'h'라는 키값을 가지고 'h번 인덱스'에서 'headgear'에 해당하는 노드에 갯수를 ++ 해줄 것이다.

   headgear의 이름이 'A'인지, 'B'인지는 상관 없이 갯수만 관리해줄 것이다. 그 이유는 밑에서 알아보도록 하자.

   그런데 의상의 종류 중에서 'headgear'만이  'h'로 시작한다는 보장이 없다. 다른 의상의 종류 중에서도, 'headgear'가

   아니면서 'h'로 시작하는 의상의 종류가 존재할 수도 있다.

   따라서 그림으로 표현하자면 다음과 같이 관리해 주었다.

  

이런식으로 의상의 종류의 가장 첫 알파벳만 따서 키 값으로 삼아주었고, 그 키에 해당하는 인덱스에 들어가보면

그 알파벳으로 시작하는 의상의 종류들이 저장되어 있고 그 각각의 노드 안에는 갯수가 있는 것이다.

"A headgear" , "B headgear" , "C face"

위에서 말한 예시대로라면 headgear 노드에는 갯수가 2개, face 노드에는 갯수가 1개가 저장될 것이다.

그럼 우리는 왜 갯수만 저장을 했을까 ??? 간단하게 생각을 해보자.

{ A , B } 라는 2개의 모자가 있다.

{ C , D } 라는 2개의 티셔츠가 있다.

나올 수 있는 조합은 총 몇개일까 ?

[ A ] , [ B] , [ C ] , [ D ] , [ A C ] , [ A D ] , [ B C ] [ B D ] 이렇게 총 8개가 존재한다.

이 8 이라는 값은 3 x 3 - 1 로 구할수가 있다. 

{ A , B } 라는 2개의 모자가 있다.

{ C } 라는 1개의 티셔츠가 있다.

{ D } 라는 1개의 하의가 있다.

나올 수 있는 조합은 총 몇개일까 ?

[ A ] [ B ] [ C ] [ D] [A C ] [ A D ] [ A C D ] [B C ] [ B D ] [ B C D ] [ C D ]

총 11개가 있다. 이 11이라는 값은 3 x 2 x 2 - 1로 구할 수 있다.

즉 ! "X 개의 의상의 종류1 이 있고, Y개의 의상의 종류2 가 있고, Z개의 의상의 종류3" 이 있다고 가정했을 때

나올 수 있는 모든 조합의 수는 (X + 1) * (Y + 1) * (Z + 1) - 1 이다.

각각의 수를 ' + 1 ' 을 해주는 것은, '선택하지 않음' 을 포함시켜준 것이다.

즉, { A , B } 라는 2개의 모자가 있다고 가정했을 때, 우리는 이 모자 중 A를 쓸 수도, B를 쓸 수도, 쓰지 않을수도 있기

때문이다. 따라서 각 의상의종류의 갯수에 +1 씩을 해서 계산을 해준 것이다.

저기서 마지막에 '1'을 빼주는 이유는 하나도 안입었을 경우, 즉, 모든 종류의 옷들 중에서 아무것도 선택하지 않은 조합일

경우이다.

즉, 이부분 때문에 의상의 이름 따위는 신경쓰지도 않고 의상의 종류와 갯수로만 관리를 해준 것이다.

[ 소스코드 ]

#include<string>
#include<vector>
 
#define TABLE_MAX 26
using namespace std;
 
struct HASH
{
    string Kind;
    int Cnt;
    HASH *Next;
};
 
HASH *HashTable[TABLE_MAX], Nodepool[35];
int N_Idx;
 
HASH *Nodeset(string S)
{
    HASH *NewNode = &Nodepool[N_Idx++];
    NewNode->Kind = S;
    NewNode->Cnt = 1;
    NewNode->Next = NULL;
 
    return NewNode;
}
 
void Hashing(int Key, string S)
{
    if (HashTable[Key] == NULL)
    {
        HASH *NewNode = Nodeset(S);
        HashTable[Key] = NewNode;
        return;
    }
    else
    {
        HASH *Iter = HashTable[Key];
        while (Iter != NULL)
        {
            if (Iter->Kind == S)
            {
                Iter->Cnt++;
                return;
            }
            Iter = Iter->Next;
        }
 
        HASH *NewNode = Nodeset(S);
        NewNode->Next = HashTable[Key];
        HashTable[Key] = NewNode;
    }
}
 
int solution(vector<vector<string>> clothes)
{
    for (int i = 0; i < clothes.size(); i++)
    {
        string S = clothes[i][1];
        int Key = S[0] - 'a';
        Hashing(Key, S);
    }
 
    vector<int> V;
    for (int i = 0; i < TABLE_MAX; i++)
    {
        if (HashTable[i] == NULL) continue;
 
        HASH *Iterator = HashTable[i];
        while (Iterator != NULL)
        {
            V.push_back(Iterator->Cnt);
            Iterator = Iterator->Next;
        }
    }
 
    int Answer = 1;
    for (int i = 0; i < V.size(); i++)
    {
        Answer = Answer * (V[i] + 1);
    }
    Answer--;
    return Answer;
}