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

[프로그래머스/LV2] 2018 KAKAO BLIND RECRUITMENT [1차] 뉴스 클러스터링

🙋‍♂️ 들어가며

이 문제를 보면 자카드 유사도인데 inner_join / outer_join 방식으로 풀 수 있다는 것을 알 수 있다

이를 이용해 문자열 유사도를 계산한다

그리고 공집합이면 J(A,B) = 1로 간주

tc-1

FRANCE -> {FR, RA, AN, NC, CE}
FRENCH -> {FR, RE, EN, NC, CH}
= 3/7 -> 0.42

tc-2

handshake -> {ha, an, nd, ds, sh, ha, ak, ke}
shake hands -> {sh, ha, ak, ke, ha, an, nd, ds}
= 8/8 -> 1

입력 조건을 보자

• 입력으로 2 <= str1, str2 <= 1000
• 입력으로 들어온 글자는 두 글자씩 끊고, 원소로 (단 영문자로 된 두글자만 유효)
• 대문자나 소문자나 동일

출력조건은 다음과 같다

• ex) 0.42 * 65536 -> int 출력

✅ 정답 코드

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

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        int N = str1.length();
        int M = str2.length();
        List<String> lst_1 = new ArrayList<>();
        List<String> lst_2 = new ArrayList<>();
        
        // 1. lst_1에 str1 원소 추가
        for (int i = 0; i < N-1; i++) {
            char ch_1 = Character.toLowerCase(str1.charAt(i));
            char ch_2 = Character.toLowerCase(str1.charAt(i+1));
            
            // 1-1. 만약 둘다 알파벳이면 lst_1에 추가
            if ( ('a' <= ch_1 && ch_1 <= 'z') && ('a' <= ch_2 && ch_2 <= 'z') ) {
                String temp = "";
                temp += ch_1;
                temp += ch_2;
                lst_1.add(temp);
            }
        }
        
        // 2. lst_2에 str2 추가
        for (int i = 0; i < M-1; i++) {
            char ch_1 = Character.toLowerCase(str2.charAt(i));
            char ch_2 = Character.toLowerCase(str2.charAt(i+1));
            
            // 2-1. 만약 둘다 알파벳이면 lst_2에 추가
            if ( ('a' <= ch_1 && ch_1 <= 'z') && ('a' <= ch_2 && ch_2 <= 'z') ) {
                String temp = "";
                temp += ch_1;
                temp += ch_2;
                lst_2.add(temp);
            }
        }
        
        
        int inner_join = 0;
        int outer_join = 0;
        
        // 3-1. inner_join 계산
        boolean[] visited = new boolean[lst_2.size()];
        for (int i = 0; i < lst_1.size(); i++) {
            String temp = lst_1.get(i);
            
            // 3-1-a. lst_2의 원소 썼는지 확인
            for (int j = 0; j < lst_2.size(); j++) {
                
                // 3-1-b. 원소를 썼다면 pass
                if (visited[j]) continue;
                
                // 3-1-c. 원소를 쓰지 않았고, lst_2가 lst_1의 원소를 갖고 있다면?
                if (lst_2.get(j).equals(temp)) {
                    inner_join++;
                    visited[j] = true;
                    break;
                }
            }
        }
        
        // 4. outer_join 계산
        outer_join = lst_1.size() + lst_2.size() - inner_join;
        
        // 5. 결과
        if (inner_join == 0 && outer_join == 0) {
            return 65536;
        }
        
        double res = (double) inner_join / outer_join;
        res *= 65536;
        answer = (int) res;
        return answer;
    }
}