문제 설명
자카드 유사도
자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.
예를 들어 집합 A = {1, 2, 3}, 집합 B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로, 집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다. 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.
자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.
제한사항
입력 형식
- 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
- 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
- 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.
출력 형식
- 입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
입출력 예
입출력 예 설명
문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.
2023.04.12
첫 번째 풀이
public int solution(String str1, String str2) {
int answer = 0;
//소문자 대문자 상관없기 때문에 소문자로 만들기
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();
//교집합
List<String> list1 = new ArrayList<>();
//차집합 + 합집합
List<String> list2 = new ArrayList<>();
//str2 리스트
List<String> list3 = new ArrayList<>();
//str1 두 단어씩 나눠서 list1, list2에 넣기
for (int i = 0; i < str1.length() - 1; i++) {
char c1 = str1.charAt(i);
char c2 = str1.charAt(i + 1);
if (c1 >= 'a' && c1 <= 'z') {
if (c2 >= 'a' && c2 <= 'z') {
list1.add(c1 + "" + c2);
list2.add(c1 + "" + c2);
}
}
}
//str2 두 단어씩 나눠서 list3에 넣기
for (int i = 0; i < str2.length() - 1; i++) {
char c1 = str2.charAt(i);
char c2 = str2.charAt(i + 1);
if (c1 >= 'a' && c1 <= 'z') {
if (c2 >= 'a' && c2 <= 'z') {
list3.add(c1 + "" + c2);
}
}
}
//값이 없다면 answer = 65536
if (list1.size() == 0 && list2.size() == 0) {
return answer = 65536;
}
//교집합 구하기
list1.retainAll(list3);
//차집합 구하기
list2.removeAll(list3);
//합집합 구하기 = 차집합과 list3 더하기
list2.addAll(list3);
//출력 값
answer = (int) (Math.floor(((double) list1.size() / (double) list2.size()) * 65536));
return answer;
}결과
- 반례에 대한 경우 추가
2023.04.13
두 번째 풀이
public int solution(String str1, String str2) {
//소문자 대문자 상관없기 때문에 소문자로 만들기
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();
//str1의 단어 리스트
List<String> list1 = new ArrayList<>();
//str2의 단어 리스트
List<String> list2 = new ArrayList<>();
//교집합 리스트
List<String> intersection = new ArrayList<>();
//합집합 리스트
List<String> union = new ArrayList<>();
//str1 두 단어씩 나눠서 list1 에 넣기
for (int i = 0; i < str1.length() - 1; i++) {
char c1 = str1.charAt(i);
char c2 = str1.charAt(i + 1);
if (c1 >= 'a' && c1 <= 'z') {
if (c2 >= 'a' && c2 <= 'z') {
list1.add(c1 + "" + c2);
}
}
}
//str2 두 단어씩 나눠서 list2 에 넣기
for (int i = 0; i < str2.length() - 1; i++) {
char c1 = str2.charAt(i);
char c2 = str2.charAt(i + 1);
if (c1 >= 'a' && c1 <= 'z') {
if (c2 >= 'a' && c2 <= 'z') {
list2.add(c1 + "" + c2);
}
}
}
Collections.sort(list1);
Collections.sort(list2);
for(String s : list1){
if(list2.remove(s)){
intersection.add(s);
}
union.add(s);
}
for(String s : list2){
union.add(s);
}
double answer = 0;
if(union.size() == 0) {
answer = 1;
} else {
answer = (double) intersection.size() / (double) union.size();
}
return (int) (answer * 65536);
}결과
통과 (추후 다시 풀어볼 것)
