[프로그래머스 - Java] [1차] 뉴스 클러스터링 (2018 KAKAO BLIND RECRUITMENT)

문제

코딩테스트 연습 - [1차] 뉴스 클러스터링

설명

자카드 유사도 구하기는 아래의 세 가지 순서로 진행된다.

 

1. 다중 집합 구하기

- 집합의 원소는 대소문자 구분 X / 영문자만 가능 (특수문자, 공백, 숫자 X)

- 두 글자씩 끊어서 ArrayList에 추가해 다중 집합을 구할 것 

-  Character.isLetter() 메소드 (char값이 문자인지 판단해 true/false 반환)를 통해 문자인지 확인

- true일 경우 다중 집합의 원소로 추가 

 

* 아래 코드 처럼 자바 정규표현식으로 Pattern.mathes 사용도 가능 

 

^	문자열 시작
$	문자열 종료
*	앞 문자가 없을 수도 있고, 무한정 많을 수도 있음
[]	문자의 집합이나 범위를 나타내고, 두 문자 사이는 -기호로 범위를 나타냄     ^가 선행하여 존재하면 not을 나타냄

 

if(Pattern.matches("^[a-zA-Z]*$", subStr)) {
	set2.add(subStr.toUpperCase());
}

 

2. 교집합 / 합집합 구하기

- 중복되는 원소가 있기에 두 집합을 오름차순으로 정렬

 

• 집합 1의 원소를 하나씩 꺼내 집합2에 포함되는지 확인

  • 집합2에 포함될 경우, 교집합에 집합 1 원소를 추가하고, 집합 2에서는 삭제

  • 집합 2에 포함되든 안되든 집합 1의 원소 합집합에 추가  

• 집합 2에 삭제되고 남아있는 모든 원소 합집합에 추가하면 끝

3. 자카드 유사도 구하기 

- 자카드 유사도는 교집합 / 합집합 

- 소수점을 봐야하기 때문에 실수형으로 계산

- 합집합의 size가 0인 공집합의 경우는 1로 처리

- 계산 값에 65536을 곱한 정수형으로 반환

전체 코드 

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
		str1 = str1.toUpperCase(); // 모두 대문자로 
		str2 = str2.toUpperCase();
		
		ArrayList<String> list1 = new ArrayList<>();
		ArrayList<String> list2 = new ArrayList<>();

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

		// str1 다중 집합 만들기 
		for(int i = 0; i < str1.length()-1; i++) {
			char a = str1.charAt(i);
			char b = str1.charAt(i+1);

			// 문자만 가진 경우만 추가 
			if(Character.isLetter(a) && Character.isLetter(b)) {
				String str = Character.toString(a) + Character.toString(b);
				list1.add(str);
			}
		}

		// str2 다중 집합 만들기 
		for(int i = 0; i < str2.length()-1; i++) {
			char a = str2.charAt(i);
			char b = str2.charAt(i+1);

			// 문자만 가진 경우만 추가 
			if(Character.isLetter(a) && Character.isLetter(b)) {
				list2.add(Character.toString(a) + Character.toString(b));
			}
        }

		// 중복 원소 처리를 위해 두 집합 정렬
		Collections.sort(list1);
		Collections.sort(list2);
		
		// 교집합 구하기 
		for(String s : list1) {
			if(list2.remove(s)) { // 집합1에 집합2가 포함된다면 삭제후, 교집합에 추가 
				intersection.add(s);
			}
			union.add(s);
		}
		
		// 합집합 구하기 
		for(String s : list2) { // 교집합에서 제외된 것 뺀 나머지 합집합에 추가 
			union.add(s);
		}
        
		// 자카드 유사도 구하기 
		double a = intersection.size();
		double b = union.size();

   		double jakard = 0;
	
		if(union.size() == 0)
			jakard = 1;	// 공집합일 경우 1
		else
			jakard = (double) intersection.size() / (double) union.size();

		return (int) (jakard * 65536);
    }
}