[프로그래머스] Level 2: 뉴스 클러스터링

https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

 

해시 맵을 사용 하여 풀었다.

코드 설명은 주석으로 대체한다.

 

교집합, 합집합을 구할 때, 한 번의 집합 순회로 구하는 방법을 생각해 봤다.

두 문자열의 총집합 수에다가 교집합을 뺀 값은 합집합이라는 결론이 나왔다.

 

 

예를 들어, 두 문자열의 집합 A와 B가 있다고 하자. (편의상 숫자로 설명)

A = { 1, 1, 2, 2, 2 }
B = { 1, 2, 2 }

교집합은, 서로 중복되는 요소를 min으로 계산한다.

따라서, { 1, 2, 2 }가 된다.

 

합집합은, 서로 중복되는 요소를 max로 계산한다.

일단, 모든 집합의 수는 8이다. (5 + 3)

 

여기서, B의 { 1 }은 A에서 { 1, 1 }이 있기 때문에, 제거된다.

이는 다르게 말하면, 같은 요소에 대해서 다른 집합에 더 큰 값이 있으면 지워진다고 볼 수 있다.

다른 집합에 더 작은 값은 그냥 min으로 계산한 값과 같다.

 

마찬가지로, B의 { 2, 2 }는 A에서 { 2, 2, 2 }가 있기 때문에, 제거된다.

그럼 결국 { 1, 1, 2, 2, 2 }만 남게 된다.

이는 총집합의 수(8) - 교집합(3)과 같다.

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

pair<unordered_map<string, int>, int> Func(const string& Str)
{
	pair<unordered_map<string, int>, int> Ret;

	for (int i = 0; i < Str.size() - 1; ++i)
	{
		// 두 글자씩 집합 만들기
		string Temp = "aa";

		Temp[0] = Str[i] > 96 ? Str[i] - 32 : Str[i];		// 편의상, 소문자를 모두 대문자로 치환
		if (Temp[0] < 65 || Temp[0] > 90) continue;		// 문자가 알파벳이 아니면 집합에 넣지 않으니, 중단

		Temp[1] = Str[i + 1] > 96 ? Str[i + 1] - 32 : Str[i + 1];
		if (Temp[1] < 65 || Temp[1] > 90) continue;

		Ret.first[Temp]++;	// 해당 집합의 개수 증가
		Ret.second++;		// 총 집합의 개수 증가
	}

	return Ret;
}

int solution(string str1, string str2) {
	// 교집합, 합집합의 수
	int Gyo = 0, Hap = 0;

	// first = 집합, 해당 집합의 중복 수
	// second = 총 집합의 수 (중복 포함)
	pair<unordered_map<string, int>, int> Save1, Save2;

	Save1 = Func(str1);	// str1의 집합 구하기
	Save2 = Func(str2);	// str2의 집합 구하기

	// 집합 A를 순회하며, 집합 B와 교집합을 찾음
	for (const auto& i : Save1.first)
		if (Save2.first.find(i.first) != Save2.first.end())
			Gyo += min(i.second, Save2.first[i.first]);

	// 두 문자열의 총 집합 수에다가 교집합을 뺀 값이 합집합이다.
	Hap = (Save1.second + Save2.second) - Gyo;

	// 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의
	if (Gyo == 0 && Hap == 0) return 65536;

	// 두 문자열의 자카드 유사도에 65536을 곱한 후에 소수점 아래를 버리고 정수부분만 출력
	return (int)(((float)Gyo / (float)Hap) * 65536);
}