[Java][프로그래머스-코딩테스트 level2] [1차] 뉴스 클러스터링

o 요구사항

입력으로 들어온 두 문자열의 자카드 유사도를 계산하고, 값에 65536을 곱한 후에 정수부만 리턴하기

자카드 유사도는 집합 간의 유사도를 검사하는 방법이다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값이다. 자카도 유사도는 집합의 중복된 원소를 허용한다.

 

o 코드진행

주어진 문자열 2개

-> 각각 소문자 변환

-> 영어로된 문자열만 List 생성

-> 두 집합의 자카드 유사도 계산

-> 정수 부분 취하기(리턴)

 

 

o 코드설계

1) 영대소문자를 구분하지 않는다 -> String 클래스의 toLowerCase() 혹은 toUpperCase() 사용

str.toLowerCase()

 

 

2-1) 주어진 문자열을 2개씩 끊어서 새로운 문자열 생성하기 -> 반복문, split() 메서드를 사용

for(int i=0; i<str.length()-1; i++){
	String t = str.substring(i, i+2);
}

 

 

 

2-2) 문자열 중에서 영문자만 포함되어야 유효함. 특수기호, 숫자, 공백이 포함된 경우 무효

.charAt() 메서드를 사용하여 영소문자만 조건에서 true를 리턴하도록 설정

조건을 만족하는 문자열은 List에 추가되도록 코드를 구성했다.

if('a' <= t.charAt(0) && t.charAt(0) <= 'z' &&'a' <= t.charAt(1) && t.charAt(1) <= 'z' ){ }

 

 

 

2-3) 위 조건을 만족하는 메서드 생성

//영어로 된 문자열만 리스트에 추가하기
List<String> getStringList(String str){
	List<String> list = new ArrayList<>();
	for(int i=0; i<str.length()-1; i++){
    		//2글자씩 끊어내기
		String t = str.substring(i, i+2);
		//앞글자, 뒷글자 모두 영소문자에 포함되어야 조건 만족
		if('a' <= t.charAt(0) && t.charAt(0) <= 'z' &&'a' <= t.charAt(1) && t.charAt(1) <= 'z' ){
			list.add(t);
		}
	}   
	list.sort(null);	 //반환하기 전에 정렬하기
	return list;
}

 

 

3) 교집합 크기 구하기

리스트간 항목을 비교한다. 미리 .sort() 메서드로 정렬하였기 때문에

바깥쪽 반복문이 진행될 때 안쪽 반복문은 index부터 시작하면 된다.

int count = 0;
int index = 0;
for(int i=0; i<listA.size(); i++){
	//이미 정렬된 List이기 떄문에 다시 인덱스0부터 비교할 필요없음
	//j 번째에 일치하는 것으로 확인되었다면 j 다음 문자열을 비교하면 됨
  for(int j=index; j<listB.size(); j++){
    if( listA.get(i).equals(listB.get(j)) ){
      count++;
      index = j+1;
      break;
    }
  }
}

 

 

 

4) 앞 단계에서 교집합 크기를 구했다면 합집합 크기는 쉽게 구할 수 있다.

A와 B의 합집합 크기 = 집합A의 크기 + 집합B의 크기 - 교집합 크기

 

 

5) 실수에서 정수부분만 취하는 것도 여러 방법이 존재한다.

여기서는 Math.floor()를 사용하였다.

 

 

o 완성코드

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

class Solution {
    public int solution(String str1, String str2) {
        //소문자로 변환 후 문자열 리스트 리턴
        List<String> listA = getStringList(str1.toLowerCase());
        List<String> listB =getStringList(str2.toLowerCase());

        //집합 크기 비교하기
        double small = compareBothList_small(listA, listB);
        double big = listA.size() + listB.size() - small;
        if(big == 0){
            return 65536;
        }
        double tmp = Math.floor(small/big* 65536);
        return (int) tmp;

    }

    //영어로 된 문자열만 리스트에 추가하기
    List<String> getStringList(String str){
        List<String> list = new ArrayList<>();
        for(int i=0; i<str.length()-1; i++){
            String t = str.substring(i, i+2);
            if('a' <= t.charAt(0) && t.charAt(0) <= 'z' &&'a' <= t.charAt(1) && t.charAt(1) <= 'z' ){
                list.add(t);
            }
        }
        list.sort(null);
        return list;
    }

    //교집합의 크기 구하기
    int compareBothList_small(List listA, List listB){
        int index = 0;
        int count = 0;
        for(int i=0; i<listA.size(); i++){
            for(int j=index; j<listB.size(); j++){
                if( listA.get(i).equals(listB.get(j)) ){
                    count++;
                    index = j+1;
                    break;
                }
            }
        }
        return count;
    }
}