문제
문자열 사이의 유사도를 검사하는 문제입니다.
두 문자열에 대해 각각 두 글자 씩 끊어서 다중집합을 만들고, 두 집합의 교집합에서 합집합을 나눈 값이 유사도입니다.
만약 문자열 “FRANCE” 와 “FRENCH”가 주어진다면 각각 (FR, RA, AN, NC, CE), (FR, RE, EN, NC, CH)의 집합이 만들어지며, 교집합은 (FR, NC), 합집합은 (FR, RA, AN, NC, CE, RE, EN, CH)가 되어 유사도는 2/8 = 0.25가 됩니다.
풀이
간단하게 집합 A = (1, 1, 2, 2, 3), 집합 B = (1, 2, 2, 4, 5) 인 경우를 생각해봅시다.
저는 각각의 집합을 key값이 숫자의 종류이고 value 값이 그 숫자의 개수를 나타내는 map 안에 넣어주도록 하겠습니다.
그러면 다음의 그림과 같은 map들이 만들어집니다.
A와 B의 교집합의 개수는 (1, 2, 2)로 3개입니다.
교집합의 개수는 mapA와 mapB에서 나온 모든 숫자들에 대해 mapA에서 나온 개수와 mapB에서 나온 개수의 최소값을 모두 더해서 구할 수 있습니다. 위의 그림처럼 1, 2, 3, 4, 5에 대해 각각 mapA에서의 개수와 mapB에서의 개수의 최소값을 모두 더해줘서 교집합의 개수 3을 구했습니다.
합집합의 개수는 반대로 max값을 모두 더해줘서 구할 수 있습니다. (1, 1, 2, 2, 3, 4, 5) 로 7개인 것을 알 수 있습니다.
이것을 이제 코드로 구현해보겠습니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <string>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define MUL 65536
using namespace std;
int solution(string str1, string str2) {
int answer = 0;
// 대문자로 변환
transform(str1.begin(), str1.end(),str1.begin(), ::toupper);
transform(str2.begin(), str2.end(),str2.begin(), ::toupper);
// key:value = 문자 : 문자개수
unordered_map<string,int> mapA;
unordered_map<string,int> mapB;
// 모든 문자 중복없이 저장하는 set
unordered_set<string> strCollector;
string temp;
// str1의 문자 map 생성
for(int i=0;i<str1.length()-1;i++){
// 연속된 두 문자가 알파벳일 경우
if((str1[i]>='A' && str1[i]<='Z') && (str1[i+1]>='A' && str1[i+1]<='Z')){
// 문자 생성
temp = str1.substr(i,2);
// map에 해당 문자 개수 1 증가
mapA[temp]++;
strCollector.insert(temp);
}
}
// str2의 문자 map 생성
for(int i=0;i<str2.length()-1;i++){
if((str2[i]>='A' && str2[i]<='Z') && (str2[i+1]>='A' && str2[i+1]<='Z')){
temp = str2.substr(i,2);
mapB[temp]++;
strCollector.insert(temp);
}
}
int inter = 0; // 교집합 개수
int un = 0; // 합집합 개수
for(auto iter:strCollector){
inter += min(mapA[iter],mapB[iter]);
un += max(mapA[iter],mapB[iter]);
}
if(inter==0 && un==0) return MUL;
answer = MUL*inter/un;
return answer;
}
