[BOJ] 백준 #9375. 패션왕 신해빈 (C++)

🎨 문제

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

• 알고리즘 분류: 자료구조, 조합론, 수학
• 난이도: Silver Ⅲ

💬 풀이

옷의 카테고리 별 개수를 세서 저장하고, 적절히 수학문제를 풀어주면 된다.
따라서 옷의 카테고리와 그 개수를 key-value쌍으로 저장할 unordered_map<string, int>을 사용한다.

1. 옷 종류별로 개수 카운트
2. 조합
   👉🏻 옷 종류별 개수들에 각각 다 1을 더한 다음,
   👉🏻 전부 곱해주고,
   👉🏻 마지막에 1 빼주면 됨 (벌거벗은 신해빈)
   
3. 젤 처음 입력받았던 테스트 케이스 개수만큼 반복

평소에 잘 안 써 버릇 했던 unordered_map에 관해 엄청간단 정리해봤다.

✔ std::unordered_map

unordered_map(해시맵)은 map처럼 key-value로 이뤄진 연관 컨테이너다.
둘은 중복을 허용하지 않는다는 점 등이 공통적이지만,
map의 요소들이 key값 기준으로 자동 정렬(오름차순)되는 반면,
unordered_map은 이름에서 알 수 있듯 정렬되지 않으며 삽입 순서대로 저장된다.

map은 내부가 BST(이진 탐색 트리)로 구현되어 삽입,삭제,조회의 시간복잡도는 $O(logn)$이다.
unordered_map은 해시함수 및 해시테이블을 기반으로 해 평균 시간복잡도가 $O(1)$다.

고딩 때 확통 문제 푸는 느낌이어서 재밌었음 ^0^/

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	int T;
	cin >> T;
	int n;
	string s[2];
	for (int i = 0; i < T; i++) {
		cin >> n;
		unordered_map<string, int> umap;
		while (n--) {
			cin >> s[0] >> s[1];
			if (umap.find(s[1]) != umap.end()) {
				++umap[s[1]];
			}
			else {
				umap.insert({ s[1], 1 });
			}
		}

		int ans = 1;
		for (auto i = umap.begin(); i != umap.end(); i++) {
			ans *= (i->second + 1);
		}
		cout << --ans << endl;
	}

	return 0;
}