[백준 BOJ][C++]9375번 패션왕 신해빈 풀이: hash

https://www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

 

 이 문제는 c++ STL map 컨테이너로 쉽게 해결할 수 있지만, 저는 해시 맵을 직접 구현해서 해결해보았습니다!

 

 size는 hashing의 원소의 개수, 즉 카테고리의 수 입니다. 

 

 hashing은 의상의 종류 category를 저장하는 string 배열입니다. 

 

 data는 hashing에서 category에 대응하는 index 위치에 의상의 이름 name을 저장하는 2차원 배열입니다. 

 

 insert 과정은 다음과 같습니다. 

 

 find_index(category)를 호출하여 hashing내에 category가 있는지 확인하고, 있다면 해당 위치의 index를 반환하고 없다면 -1을 반환합니다. 

 

 이제 이 반환값을 가지고 -1이라면 기존에 없던 카테고리라는 뜻이므로 hashing에 category를 추가하고 size를 증가시킵니다. 그리고 data[size] 벡터에 의상의 이름 name을 push 합니다. 

 

 반환값이 -1이 아니라면 이미 이 카테고리가 생성되었다는 의미이므로 반환값 idx위치 data[idx]에 의상의 이름 name을 push 합니다. 

 

 이제 해시 맵 완성입니다!

 

 solution()은 입을 수 있는 의상의 경우의 수를 계산하는 함수입니다. 

 

 headgear : hat, turban -> 2개

 eyewear : sunglasses -> 1개 

 

 머리 x 눈 = (headgear의 수 + 1) * (eyewear의 수 + 1) - 1(둘 다 안 입는 경우) 이 됩니다. 

 

#include<iostream>
#include<algorithm>
#include<array>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<string>

using namespace std;

class hash_map {
	vector<string> data[31];
	string hashing[31];
	int size;

public:
	hash_map() {
		size = 0;
	}

	int find_index(string category) {

		if (size == 0) {
			hashing[0] = category;
			size++;
			return 0;
		}
		
		for (int i = 0; i < size; i++) {
			if (hashing[i].compare(category) == 0) {
				return i;
			}
		}
		return -1;
	}

	void insert(string name, string category) {

		int idx = find_index(category);

		if (idx == -1) {
			hashing[size] = category;
			data[size].push_back(name);
			size++;
		}
		else {
			data[idx].push_back(name);
		}
	}

	void print() {
		for (int i = 0; i < size; i++) {
			cout << "category " << hashing[i] << ": ";
			for (int j = 0; j < data[i].size(); j++) {
				cout << data[i][j] << " ";
			}
			cout << endl;
		}
	}

	int solution() {
		int ans = 1;

		for (int i = 0; i < size; i++) {
			ans *= (data[i].size() + 1);
		}
		return ans - 1;
	}
};

int main(void) {

	int t, n;

	scanf("%d", &t);

	while (t > 0) {

		scanf("%d", &n);
		hash_map map;

		string s1, s2;

		for (int i = 0; i < n; i++) {
			cin >> s1 >> s2;
			map.insert(s1, s2);
		}

		map.print();

		cout << map.solution() << endl;

		t--;
	}

	return 0;
}