뉴스 클러스터링

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

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

---

이 문제에서 어려운 점은 각 문자열에서 중복되는 문자열이 있을 경우에, 교집합과 합집합의 길이를 구하는 것이었습니다. 만약에 A = {1, 1, 1, 2, 2, 3} 이고, B = {1, 2, 2, 2, 4, 5} 이라면, A에서 중복되는 1의 갯수가 3개이고, B에서 중복되는 갯수가 1개 입니다. 또, 중복되는 2의 갯수가 A에서는 2개, B에서는 3개 입니다. 그 중에서 1은 작은 갯수인 1개를 교집합에 넣고, 큰 갯수인 3을 합집합에 넣고, 2는 작은 갯수인 2개를 교집합에, 큰 갯수인 3개를 합집합에 넣기 때문에, 

A∩B = { 1, 2, 2 }     A∪B = { 1, 1, 1, 2, 2, 2, 3, 4, 5 } 가 됩니다.

중복되는 문자열의 처리만 잘 하면 자카드 유사도를 구할 수 있습니다.

< 문제 풀이 >

1. str1 과 str2 에서 문자열을 정제해서 넣기 위해 ArrayList 를 선언했습니다. 대소문자 구분이 없기 때문에, 주어진 str1 과 str2를 저는 모두 소문자로 바꿨습니다. 그리고 ArrayList 에 넣을 때 check 라는 함수를 따로 만들어서, 영문자로만 된 글자 쌍만 넣을 수 있게 했습니다.

2. 그리고 교집합과 합집합을 구하기 위해 ArrayList 로 intersection(교집합) 과 union(합집합)을 선언하고, intersection 에 일단 먼저 교집합을 구하는데, list1 과 list2 에서 일단 겹치고, 중복되는 문자쌍을 하나로 보고 넣었습니다.

3. 그리고 분자가 되는 inter 변수와 분모가 되는 uni 변수를 선언 했습니다. 중복되는 문자열 중에 최솟값을 inter에 더하고, 최댓값을 union 에 더해야 하기 때문에, intersection 에 있는 교집합 문자쌍들을 list1, list2와 비교했습니다. 여기까지 수행했을 경우에 분자가 되는 inter 변수가 완성 됩니다.

4. 그리고 교집합이 아닌 list1 과 list2에서 서로 다른 문자쌍들을 구해서 union 에 넣어주고, 마지막에 uni 변수에 union의 size 를 더해주었습니다.

5. 여기까지 했을 경우에 주어진 케이스5와 13이 틀리다고 나왔습니다. 그래서 질문하기를 눌렀는데, 저와 같은 사람이 있어서 힌트를 얻어 해결했습니다. 분모(inter)가 0인 경우에는 답이 0이 나오고, 분모(uni)가 0인 경우에는 답이 65536 이 나와야합니다.

---

import java.util.ArrayList;
import java.util.Collections;

class Solution {
  public int solution(String str1, String str2) {
        int answer = 0;

		ArrayList<String> list1 = new ArrayList<String>();
		ArrayList<String> list2 = new ArrayList<String>();

		str1 = str1.toLowerCase();
		str2 = str2.toLowerCase();

		for (int i = 0; i < str1.length() - 1; i++) {
			if (check(str1.substring(i, i + 2))) {
				list1.add(str1.substring(i, i + 2));
			} else
				continue;
		}

		for (int i = 0; i < str2.length() - 1; i++) {
			if (check(str2.substring(i, i + 2))) {
				list2.add(str2.substring(i, i + 2));
			} else
				continue;
		}

		
		// Collections.sort(list1);
		// Collections.sort(list2);

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

		
		// 교집합 구하기
		for (int i = 0; i < list1.size(); i++) {
			Outter: for (int j = 0; j < list2.size(); j++) {
				if (list1.get(i).equals(list2.get(j))) {
					
					for (int k = 0; k < intersection.size(); k++) {
						if ((intersection.get(k)).equals(list1.get(i))) {
							continue Outter;
						}
					}
					
					intersection.add(list1.get(i));
					continue;
				}
			}

		}
		
		
		int inter = 0;
		int uni = 0;
		
		for(int i=0; i<intersection.size(); i++) {
			int n1 = 0;
			int n2 = 0;
			for(int j=0; j<list1.size(); j++) {
				if(intersection.get(i).equals(list1.get(j))) {
					n1++;
				}
			}
			
			for(int j=0; j<list2.size(); j++) {
				if(intersection.get(i).equals(list2.get(j))) {
					n2++;
				}
			}
			inter += Math.min(n1, n2);
			uni += Math.max(n1, n2);
		}
		
//		System.out.println("inter : " + inter);
//		System.out.println("uni : " + uni);
	
		// 합집합 구하기. 1. list1에서 intersection에 없는 원소들 다 넣기
		Outter : for(int i=0; i<list1.size(); i++) {
			for(int j=0; j<intersection.size(); j++) {
				if(list1.get(i).equals(intersection.get(j))) {
					continue Outter;
				}
			}
			union.add(list1.get(i));
		}

		// 합집합 구하기. 2. list2에서 intersection에 없는 원소들 다 넣기
		Outter : for(int i=0; i<list2.size(); i++) {
			for(int j=0; j<intersection.size(); j++) {
				if(list2.get(i).equals(intersection.get(j))) {
					continue Outter;
				}
			}
			union.add(list2.get(i));
		}
		
		uni += union.size();
		
		if(uni == 0) {
			return 65536;
		}
		
		answer = (int)((double)inter/(double)uni * 65536);
		

		return answer;
  }
    public static boolean check(String st) {
		char[] arr = st.toCharArray();
		
		for(int i=0; i<arr.length; i++) {
			if((arr[i] >= 65 && arr[i] <=90) || (arr[i] >=97 && arr[i] <= 122)) {
				continue;
			} else {
				return false;
			}
		}	
		return true;
	}
}