[ 알고리즘 ] 코딩 - Programmers - 뉴스클러스터링.java

---

문제 링크

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

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

---

* 프로그래머스 - Level2 - (자바)뉴스 클러스터링

- 문자열다루기 / List다루기

입출력예시

 

---

< 로직 >

* 처음에는 HashMap을 이용해서 중복 체크를 하려고 했는데, 생각보다 효율이 나오지 않았다.

* 그래서 HashMap을 두개의 List로 변경했다

* 문자열 모두 소문자로 변경

* 각 문자열을 2덩이씩 분리해서 리스트에 저장

* 두개의 리스트 중 하나를 기준삼아 다른 쪽 리스트의 중복 요소를 제거

* 제거함과 동시에 중복 카운트 + 1

* 제거하든 하지않든 합집합 전체 길이 카운트 + 1

* 기준 리스트의 작업이 모두 끝나고 다른 리스트의 남은 길이를 전체 길이에 카운트

* 중복 카운트 / 전체 카운트 * 65536 하면 정답! 

---

import java.util.LinkedList;
import java.util.List;

class Solution {
	    double duplicate, length;
	    public int solution(String str1, String str2) {
	        // 리스트을 이용해서 해결하자!
	    	List<String> str_list_one = new LinkedList<String>();
	    	List<String> str_list_two = new LinkedList<String>();
	    	
	    	str1 = str1.toLowerCase();
	    	str2 = str2.toLowerCase();
	    	
	        // str1과 str2를 2덩이씩 나눈 다음
	    	// 각 리스트에 맞게 배치
	        divide(str1, str_list_one);
	        divide(str2, str_list_two);
	        
	        // 중복개수와 합했을때의 길이를 구해보자
	        find(str_list_one, str_list_two);
	    	
	        // 중복 개수 / 전체길이 하면 될 거 같다
	        if(length == 0) return 65536;
	        double calc = duplicate/length;
	        int answer = (int)(calc*65536);
	        return answer;
	    }

	    /*
	     * 중복값(교집합)과 전체길이(합집합)를 구하자
	     * */
		private void find(List<String> str_list_one, List<String> str_list_two) {
			for(String key : str_list_one) { // 리스트 하나를 기준으로 삼아 다른 리스트 항목을 제거하는 형식
				if(str_list_two.contains(key)) { // 요소가 있으면
					str_list_two.remove(key); // 제거
					duplicate++; // 중복 + 1
				}
				length++; // 전체 길이 + 1
			}
			
			length += str_list_two.size(); // 중복이 아닌 나머지 값이 남아 있는 경우 그만큼 더해주자
		}

		/*
		 * 문자열 자르기 로직
		 * */
		private void divide(String str, List<String> str_list) {
			for(int i = 0; i < str.length(); i++) {
				StringBuilder sb = new StringBuilder();
				for(int j = 0; j < 2; j++) {
					if(i+j < str.length()) {
						char next_char = str.charAt(i+j);
						if('a' <= next_char && next_char <= 'z')
							sb.append(next_char);
						
					}
				}
				if(sb.length() > 1) { // 알파벳이 아닌 경우를 만나면 길이가 1일 것.
					str_list.add(sb.toString());
				}
			}
		}
	}