[프로그래머스] 뉴스 클러스터링 (Java)

프로그래머스 뉴스 클러스터링

문제풀이

문제 지문이 어렵게 나와있어서 굉장히 어려울 것 같았는데 생각보다 쉬웠다. 간단하게 주어진 두 개의 문자열 사이의 자카드 유사도를 구하면 되는 문제다.

• 자카드 유사도 구하기
  • 문제에 따르면 자카드 유사도는 두 집합 사이의 교집합 / 합집합이다.
  • 먼저, 두 문자열의 다중집합을 구한다. (두 문자씩 끊어서 만든다)
    • 소문자, 대문자를 구분하지 않는다.
    • 영문자만 유효하다.
  • 두 집합의 교집합과 합집합을 구한다.
    • 중복원소의 처리를 위해 먼저 두 집합을 정렬한다.
    • 집합1의 원소를 하나씩 꺼내서 집합2에 포함되는지 확인한다.
      • 집합2에 포함된다면 교집합에 넣고 집합2에서 삭제한다.
      • 집합2에 포함됨과 상관없이 합집합에 넣는다.
    • 집합2에 남아있는 원소를 합집합에 모두 넣는다.
  • 실수형의 자카드 유사도를 구하고 65536을 곱한 후 정수형으로 변환한다.

구현코드

import java.util.*;

class Solution {
  public int solution(String str1, String str2) {
      ArrayList<String> multiSet1 = new ArrayList<>();
      ArrayList<String> multiSet2 = new ArrayList<>();
      ArrayList<String> union = new ArrayList<>();
      ArrayList<String> intersection = new ArrayList<>();
      
      str1 = str1.toLowerCase();
      str2 = str2.toLowerCase();
      
      for(int i = 0 ; i < str1.length() - 1 ; ++i){
          char first = str1.charAt(i);
          char second = str1.charAt(i + 1);
          
          if(first >= 'a' && first <= 'z' &&
             second >= 'a' && second <= 'z'){
              multiSet1.add(first + "" + second);
          }
      }
      
      for(int i = 0 ; i < str2.length() - 1 ; ++i){
          char first = str2.charAt(i);
          char second = str2.charAt(i + 1);
          
          if(first >= 'a' && first <= 'z' &&
             second >= 'a' && second <= 'z'){
              multiSet2.add(first + "" + second);
          }
      }
      
      Collections.sort(multiSet1);
      Collections.sort(multiSet2);
            
      for(String s : multiSet1){
          if(multiSet2.remove(s)){
            intersection.add(s);
          }
          union.add(s);
      }
      
      for(String s : multiSet2){
          union.add(s);
      }
      
      double jakard = 0;
      
      if(union.size() == 0) {
          jakard = 1;
      } else {
          jakard = (double)intersection.size() / (double)union.size();
      }
            
      return (int)(jakard * 65536);
  }
}