문제
문제분석
두개의 문자열로부터 원소들을 추출하고 교집합과 합집합을 구한후 자카드수를 구하는 문제이다.
일반적인 합집합, 교집합과는 다르게 양쪽에 여러개가 존재할 시 합집합은 많은 쪽을, 교집합은 적은 쪽 수를 맞춘다.
풀이
처음에 원소들을 중복해 나열하여 교집합과 합집합 구할때 여러번 다시 입력하려 하였으나, 다시 세는게 불가능하여 해쉬맵을 이용하였다. Key는 2글자의 문자이고 ,Value는 나온 횟수이다.
풀이 단계
1.문자열에서 원소 추출하기
2.교집합과 합집합 구하기
3.자카드수 구하기
문자열에서 원소 추출하기
같은 원소가 여러개 나올수 있으므로
HashMap<String,Integer> arr1 = new HashMap<>(); //str1의 원소와 횟수
HashMap<String,Integer> arr2 = new HashMap<>(); //str2의 원소와 횟수
//str1의 원소와 횟수
for(int i=1;i<str1.length();i++){
if(Character.isLetter(str1.charAt(i-1)) && Character.isLetter(str1.charAt(i))){
String key = str1.substring(i-1,i+1).toUpperCase(); //모두 대문자로
if(!arr1.containsKey(key))
arr1.put(key,1);
else
arr1.put(key,arr1.get(key)+1);
}
}
//str2의 원소와 횟수
for(int i=1;i<str2.length();i++){
if(Character.isLetter(str2.charAt(i-1)) && Character.isLetter(str2.charAt(i))){
String key = str2.substring(i-1,i+1).toUpperCase(); //모두 대문자로
if(!arr2.containsKey(key))
arr2.put(key,1);
else
arr2.put(key,arr2.get(key)+1);
}
}먼저 문자인지 아닌지를 구분하는 API Character.isLetter()를 이용해 두개의 문자가 모두 알파벳인지 확인한다.
모두 알파벳이면 해시에 추가한다. 이때 처음나오면 단순히 1을 이미 있으면 해시.get(키)+1을 하여 +1해준다.
교집합과 합집합 구하기
HashMap<String,Integer> inter = new HashMap<>(); //교집합의 원소와 횟수
HashMap<String,Integer> union = new HashMap<>(); //합집합의 원소와 횟수
//교집합의 원소와 횟수
Iterator<String> keys = arr1.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
int value = 0; //안나오면 0
if(arr2.containsKey(key)) //str2에도 있다면
value = arr2.get(key); //나온 횟수 저장
int intersection = Math.min(arr1.get(key),value); //str1과 str2중 적게 나온 횟수 저장
if(intersection > 0) //둘다 존재한다면
inter.put(key,intersection); //최솟값 저장
}
//합집합의 원소와 횟수
keys = arr1.keySet().iterator();
while(keys.hasNext()){ //str1 모두 저장
String key = keys.next();
union.put(key,arr1.get(key));
}
keys = arr2.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
int value = arr2.get(key);
if(union.containsKey(key)){ //str1에도 존재
if(value > union.get(key)) //횟수가 더많으면
union.put(key,value); //바꿈
}else{ //str1에 없고 str2에만 존재
union.put(key,value);
}
}교집합과 합집합은 arr1을 기준으로 먼저하고 arr2로 비교하는 점에선 크게 다르지 않다.
우선 교집합은 arr1에도 존재하는 arr2의 요소를 찾아 arr1의 횟수와 arr2의 횟수중 작은 수를 교집합 해시맵에 추가한다.
다음 합집합은 arr1의 모든 요소를 합집합 해시맵에 추가하고 arr2의 요소 중 arr1에도 존재하고 횟수도 더많은 요소와 arr1에는 존재하지 않는 요소를 해시맵에 추가한다.
자카드수 구하기
double answer = 0;
int inters = 0; //교집합 수
int unions =0; //합집합 수
//교집합의 수
keys = inter.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
inters += inter.get(key);
}
//합집합의 수
keys = union.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
unions += union.get(key);
}
//자카드 유사도
if(unions == 0)
answer = 1;
else{
answer = (double)inters / (double)unions;
}
answer *= 65536; 자카드 교집합수는 모든 교집합 원소의 수 / 모든 합집합 원소의 수 로 합집합과 교집합의 수는 해시맵에 존재하는 원소들의 횟수를 모두 더하면 구할수 있다.
코드
import java.util.*;
class Solution {
public int solution(String str1, String str2) {
double answer = 0;
int inters = 0; //교집합 수
int unions =0; //합집합 수
HashMap<String,Integer> arr1 = new HashMap<>(); //str1의 원소와 횟수
HashMap<String,Integer> arr2 = new HashMap<>(); //str2의 원소와 횟수
HashMap<String,Integer> inter = new HashMap<>(); //교집합의 원소와 횟수
HashMap<String,Integer> union = new HashMap<>(); //합집합의 원소와 횟수
//str1의 원소와 횟수
for(int i=1;i<str1.length();i++){
if(Character.isLetter(str1.charAt(i-1)) && Character.isLetter(str1.charAt(i))){
String key = str1.substring(i-1,i+1).toUpperCase(); //모두 대문자로
if(!arr1.containsKey(key))
arr1.put(key,1);
else
arr1.put(key,arr1.get(key)+1);
}
}
//str2의 원소와 횟수
for(int i=1;i<str2.length();i++){
if(Character.isLetter(str2.charAt(i-1)) && Character.isLetter(str2.charAt(i))){
String key = str2.substring(i-1,i+1).toUpperCase(); //모두 대문자로
if(!arr2.containsKey(key))
arr2.put(key,1);
else
arr2.put(key,arr2.get(key)+1);
}
}
//교집합의 원소와 횟수
Iterator<String> keys = arr1.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
int value = 0; //안나오면 0
if(arr2.containsKey(key)) //str2에도 있다면
value = arr2.get(key); //나온 횟수 저장
int intersection = Math.min(arr1.get(key),value); //str1과 str2중 적게 나온 횟수 저장
if(intersection > 0) //둘다 존재한다면
inter.put(key,intersection); //최솟값 저장
}
//합집합의 원소와 횟수
keys = arr1.keySet().iterator();
while(keys.hasNext()){ //str1 모두 저장
String key = keys.next();
union.put(key,arr1.get(key));
}
keys = arr2.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
int value = arr2.get(key);
if(union.containsKey(key)){ //str1에도 존재
if(value > union.get(key)) //횟수가 더많으면
union.put(key,value); //바꿈
}else{ //str1에 없고 str2에만 존재
union.put(key,value);
}
}
//교집합의 수
keys = inter.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
inters += inter.get(key);
}
//합집합의 수
keys = union.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
unions += union.get(key);
}
//자카드 유사도
if(unions == 0)
answer = 1;
else{
answer = (double)inters / (double)unions;
}
answer *= 65536;
return (int)answer;
}
}GitHub
오늘도 내일도 화이팅!