[프로그래머스][1차][뉴스 클러스터링]

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

프로그래머스

 

문제

문자열 사이의 유사도를 계산하여라.

문자열 "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가 된다.

 

입력형식 

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이 때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

출력형식

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

 

예제 입출력

 

풀이

문자열이 대, 소문자를 가리지 않기 때문에 toLowerCase()를 사용하여  전부 소문자로 만들고 ArrayList에 두 글자씩 넣을 예정입니다. 

	tstr1 = str1.toLowerCase();
	tstr2 = str2.toLowerCase();
	
	ArrayList list1 = new ArrayList<>();
	ArrayList list2 = new ArrayList<>();

 

각 단어가 특수 문자가 아니고, 소문자 인지를 판단하고 단어 두 글자가 소문자 이면 각각 list1, list2에 넣어준다.

for (int i = 0; i < str1.length() - 1; i++) {
    if ((tstr1.charAt(i) >= 97 && tstr1.charAt(i) <= 122) 
         && (tstr1.charAt(i + 1) >= 97 && tstr1.charAt(i + 1) <= 122)) {
            list1.add(tstr1.substring(i , i + 2));
    }
}
	
for (int j = 0; j < str2.length() - 1; j ++) {
    if ((tstr2.charAt(j) >= 97 && tstr2.charAt(j) <= 122) 
        && (tstr2.charAt(j + 1) >= 97 && tstr2.charAt(j + 1) <= 122)) {
            list2.add(tstr2.substring(j, j + 2));
    }
}

 

각 list1, list2의 크기가 둘 다 '0'이면 교집합, 합집합의 크기가 0 이기에 65536의 값을 리턴한다.

if (list1.size() == 0 && list2.size() == 0) {
    answer = 65536;
    return answer;
}

 

list1, list2의 크기를 구해서 임시 합집합의 값을 구한다.

list1에 list2의 값이 있으면 교집합의 값을 1 추가하고, 합집합의 값을 1 빼준다.

for 문을 돌면서 list2의 값이 중복 체크 될 수 있기에 같은 값이 나온 것 list2에서 remove 해준다.  

total = list1.size() + list2.size();
	
for(int i = 0; i < list1.size(); i++) {
     for(int j = 0 ; j < list2.size(); j++) {
          if (list1.get(i).equals(list2.get(j)) == true) {
               bro++;         //교집합의 값
               total--;       //합집합의 값
               list2.remove(j);
               break;
          }
     }
}     

 

bro와 total의 값은 정수이기에 소수점을 구하기 위해서 total에 (dobule)을 붙혀 주었다.

answer 값은 정수를 구하기에 (int)를 붙어 주었다.

    tansw = bro / (double)total;
    answer = (int) (tansw * 65536);
      
    return answer;

 

전체 코드

import java.util.*;

class Solution {
  public int solution(String str1, String str2) {
    String temp = "", tstr1 = "", tstr2 = "";
	int answer = 0, total = 0, bro = 0;
	double tansw = 0;
	
	tstr1 = str1.toLowerCase();
	tstr2 = str2.toLowerCase();
	
	ArrayList list1 = new ArrayList<>();
	ArrayList list2 = new ArrayList<>();
	
	for (int i = 0; i < str1.length() - 1; i++) {
		if ((tstr1.charAt(i) >= 97 && tstr1.charAt(i) <= 122) 
				&& (tstr1.charAt(i + 1) >= 97 && tstr1.charAt(i + 1) <= 122)) {
			list1.add(tstr1.substring(i , i + 2));
		}
	}
	
	for (int j = 0; j < str2.length() - 1; j ++) {
		if ((tstr2.charAt(j) >= 97 && tstr2.charAt(j) <= 122) 
				&& (tstr2.charAt(j + 1) >= 97 && tstr2.charAt(j + 1) <= 122)) {
			list2.add(tstr2.substring(j, j + 2));
		}
	}
	
	if (list1.size() == 0 && list2.size() == 0) {
		answer = 65536;
		return answer;
	}
			
	total = list1.size() + list2.size();
	
	for(int i = 0; i < list1.size(); i++) {
		for(int j = 0 ; j < list2.size(); j++) {
			if (list1.get(i).equals(list2.get(j)) == true) {
				bro++;
				total--;
				list2.remove(j);
				break;
			}
		}	
	}
      
	tansw = bro / (double)total;
	answer = (int) (tansw * 65536);
      
	return answer;

  }
}