9375 풀이

※ 문제 링크 : https://www.acmicpc.net/problem/9375

이 문제는 어떤 자료구조로 어떻게 사용할 것인가?를 중점으로 하는 문제입니다. 이 문제를 푸는 데 가장 중점적인 기능을 하는 변수는 data랑 index 입니다. 여기서 저는 의상의 이름과 종류에서 의상의 이름은 unordered_map을 사용하기 때문에 제외하기로 하였습니다. 따라서 index에는 의상의 종류와 unordered_map에는 동일 의상 종류(key)에 속하는 것들이 몇 개(value)가 있는 지를 받았습니다.

그 다음으로 수학적 개념을 활용을 했습니다. 이를 테면, 아래와 같은 입력인 경우를 생각해보겠습니다.

hat headgear
sunglasses eyewear
turban headgear

이 경우, 저는 다음과 같은 생각으로 접근하였습니다. “headgear 2개의 가능성과 안입는 것 한 가지 가능성 중 하나를 고르는 경우의 수” 그리고 “eyewear 1개의 가능성과 안입는 것 한 가지의 가능성 중 하나를 고르는 경우의 수”을 생각했습니다. 이를 수학적으로 표현을 하면 아래와 같게 됩니다.

\((\binom{3}{1} \times \binom{2}{1})\) 전자는 headgear의 가능성이고, 후자는 eyewear의 가능성이 됩니다. 이렇게 만들어지는 가능성을 전부 나열을 하면 아래와 같이 됩니다.(None은 아무것도 입지 않음을 이야기 합니다.)

하지만 문제에서 아무것도 입지 않는 경우는 없다 하였으므로 (None, None)인 경우를 제외해주도록 합니다. 그러면 결과적으로 위의 입력에 대한 결과 수식은 아래와 같이 됩니다. \((\binom{3}{1} \times \binom{2}{1}) - 1\) 이를 이제 소스코드로 나타내면 아래와 같이 됩니다.

#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;

int main(void){
    int t; cin >> t;
    for(int i = 0; i < t; i++){
        unordered_map<string, int> data;
        int n; cin >> n;
        for(int i = 0; i < n; i++){ // 입력을 받는 부분
            string __name__; string kind; // name은 사용되지 않습니다.
            cin >> __name__ >> kind;
            if(data.find(kind) == data.end()){ // 데이터가 없는 경우
                data.insert({kind,1});
            }
            else{ // 데이터가 있는 경우
                data[kind]++;
            }

        }
        int result = 1; // 곱셈을 위한 초기값
        for(auto kind : data ){
        	// second는 해당 종류가 가지는 가짓 수
            result *= (kind.second + 1);
        }
        result -= 1; // 모두가 None인 케이스 제외
        cout << result << endl;
    }
    return 0;
}