[백준 9375번 C++] 패션왕 신해빈 (해시, Map/Set)

문제

문제 분석

문제를 잘 읽는 것이 중요하다.

먼저 의상마다 한 가지의 종류씩을 골라서 입을 수 있다.

문제에서 나온 예제 입력을 바탕으로 설명하자면,

headgear는 {hat, turban}을 고를 수 있고 아무것도 선택하지 않을 수 있다. 총 경우의 수는 3가지이다.

eyewear은 {sunglasses}을 고를 수 있고 아무것도 선택하지 않을 수 있다. 총 경우의 수는 2가지이다.

즉, 해빈이가 입을 수 있는 모든 의상의 경우의 수는 3*2인 6가지이다. 하지만 문제 조건에서 아무 것도 입지 않는 경우는 제외하기로 했다. headgear와 eyewear 에서 아무것도 선택하지 않는 경우 1가지를 뺀 총 5가지가 정답이다.

이러한 아이디어를 바탕으로 구현하면 된다.

정답 코드

- unordered_map을 통해 의상 종류에 따른 의상 수를 담아 해결한다. 특히 map/set은 마치 인덱스처럼 접근할 수 있다는 장점이 있어 key 값의 개수를 셀 때 유용하다.

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		unordered_map<string, int> um;
		int cloth_cnt;
		cin >> cloth_cnt;
		for (int j = 0; j < cloth_cnt; j++) {
			string cloth_name;
			string category; // 분류
			cin >> cloth_name >> category;
			// 같은 이름을 가진 의상은 존재하지 않는다고 하였으므로 이 부분은 따지지 않아도 됨.
			um[category]++; // 해당 의상 종류 수를 더해준다.
		}
		// 모든 의상들에 대해 (해당 의상 종류 수 + 1) 을 곱해준다.
		int ans = 1; // 곱해야 하므로 1로 두고 시작한다. 0으로 하면 어떤 수를 곱해도 0이 나온다.
		unordered_map<string, int>::iterator iter;
		for (iter = um.begin(); iter != um.end(); iter++) {
			ans *= iter->second + 1;
		}

		cout << ans - 1 << "\n"; // 아무 것도 의상을 입지 않는 경우는 없으므로 이 경우의 수 1개를 빼준다.
	}
	

	return 0;
}