[BaekJoon/백준] 9375번 (C++ MAP 사용/ 조합문제 / 다시보기)

어려웠다. 못풀었다. 수학의 바닥이 참혹하게 느껴졌다.

 

풀이를 검색했고, 새로운 발상을 알게 되었으며, MAP 이라는 자료구조도 알게되었다.

 

풀이를 알게 된 뒤, C로 풀어나가려 했으나.. 도저히 효율적으로 풀어나갈 수 없겠어서, C++로 MAP을 사용해 코드를 작성했다.

+ 풀이는 주석에 간단하게 정리했다

#include <iostream>
#include <string>
#include <map>

using namespace std;

int T, N;

int main() {
    
    int result;
    
    cin >> T;
    
    map<string, int> m; // key = string, key value = int
    string clothes, kind;
    
    map<string, int>::iterator iter; // map<string, int> iterator ( = pointer )

    
    while(T--) {
        
        // 테스트 케이스마다 초기화
        result = 1;
        m.clear();
        
        // 입력
        cin >> N;
        
        while(N--) {
            
            cin >> clothes >> kind;
            
            m[kind]++; // key를 kind로 갖고 있는 데이터의 value 1 증가

            
        }
                
        // map<string ,int>::iterator을 통해, 시작부터 끝까지 돎
        for(iter = m.begin(); iter != m.end(); iter++) {
            result *= iter->second + 1;
        }
        cout << result - 1 << endl;
    }
        
}

/*
 
 예제 입력을 예시로 설명
 
 hat headgear
 sunglasses eyewear
 turban headgear
 
 
 위를 분류해보자
 
 headgear : hat, turban
 eyewear : sunglasses
 
 안입는경우 추가
 
 headgear : hat, turban, X
 eyewar : sunglasses, X
 
 하나씩 1:1 대응해보면
 
 1. hat, X
 2. turban, X
 3. X, sunglasses
 4. X, X
 5. hat, sunglasses
 6. turban, sunglasses
 
 총 경우의 수 = 3C1 x 2C1
 
 여기서, 문제에서 주어진 예제 정답이 1,2,3,5,6에 나타남을 알 수 있다.
 
 
 문제 답 : 3C1 x 2C1 - 1(옷을 아무것도 안입는 경우)
  
 */