문제

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

---

입력

• 입력으로는 str1과 str2의 두 문자열이 들어온다.

---

출력

• 입력으로 들어온 두 문자열의 자카드 유사도를 출력한다.

---

풀이

제한조건

• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다.

접근방법

단순 구현

1. 문자열을 끊어서 다중 집합 만들기.
2. 교집합과 합집합 생성하기

크게 2가지만 구현 하면 된다.

1. 문자열을 끊어서 다중 집합 만들기.
문자열을 2개씩 잘라내보자.
문자열에는 특수문자 또는 숫자가 포함될 수 없다.
따라서 알파벳만으로 이루어진 문자열만 고르면 된다.

private List<String> getTokenList(String str) {
	int len = str.length();
	List<String> list = new ArrayList<>();
	for (int i = 0; i < len - 1; ++i) {
		if (isAlphabet(str.charAt(i)) && isAlphabet(str.charAt(i + 1)))
			list.add(str.substring(i, i + 2));
	}
	return list;
}

private boolean isAlphabet(char c) {
	if ('a' <= c && c <= 'z')
		return true;
	return false;
}

2. 교집합과 합집합 생성하기
문제를 읽어보면 교집합에서는 min값을 이용하고, 합집합인 경우 max값을 이용해서 구함을 알 수 있다.

이를 조금 다르게 해석해보면, 중복되는 원소가 생겼을때, 양쪽 List에서 모두 지워주는 방식으로 사용한다면 동일하게 사용할 수 있다.

교집합 -> 첫 번째 그룹의 원소와 두 번째 그룹의 원소가 겹치는 것만 교집합에 넣고 두 번째 그룹에서 지워준다.
합집합 -> 첫 번째 그룹의 원소를 모두 넣고, 교집합을 만들고 남은 두 번째 그룹의 모든 원소를 추가로 넣는다.

---

코드

import java.util.ArrayList;
import java.util.List;

public class Solution {
	public int solution(String str1, String str2) {
		List<String> group1 = getTokenList(str1.toLowerCase());
		List<String> group2 = getTokenList(str2.toLowerCase());

		List<String> intersection = new ArrayList<>();
		List<String> union = new ArrayList<>();

		for (String token : group1) {
			if (group2.contains(token)) {
				intersection.add(token);
				group2.remove(token);
			}
			union.add(token);
		}
		union.addAll(group2);

		if(union.size()== 0)
			return 65536;
		return (int)(65536 * intersection.size() / union.size());
	}

	private List<String> getTokenList(String str) {
		int len = str.length();
		List<String> list = new ArrayList<>();
		for (int i = 0; i < len - 1; ++i) {
			if (isAlphabet(str.charAt(i)) && isAlphabet(str.charAt(i + 1)))
				list.add(str.substring(i, i + 2));
		}
		return list;
	}

	private boolean isAlphabet(char c) {
		if ('a' <= c && c <= 'z')
			return true;
		return false;
	}

}