[프로그래머스] [1차] 뉴스 클러스터링

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

 

https://school.programmers.co.kr/learn/courses/30/lessons/17677?language=java

프로그래머스

---

Think🤔

 

import java.util.ArrayList;

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

        double jaka = 0;
        
        ArrayList<String> arr1 = new ArrayList();
        ArrayList<String> arr2 = new ArrayList();
        
        for(int i=0; i<str1.length() - 1; i++){
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr1.add(""+c1+c2);
            }
        }
        
        for(int i=0; i<str2.length() - 1; i++){
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr2.add(""+c1+c2);
            }
        }
        
        ArrayList<String> intersection = new ArrayList<>(arr1);
        intersection.retainAll(arr2); // arr1과 arr2의 교집합을 intersection에 저장
        
        int kyo = intersection.size();
        int hab = arr1.size() + arr2.size() - kyo;
        
        if(intersection.size() == 0){
            answer = 65536;
        } else {
            answer = (int)((double) kyo / hab * 65536);
        }
        
        System.out.println(arr1);
        System.out.println(arr2);
        System.out.println("kyo : " + kyo);
        System.out.println("hab : " + hab);
        
        return answer;
    }
}
// ab+면 요소를 하나로 삼음
// ab+ -> ab
// abc -> ab bc 

// 유사도 체크 후 정수 버리고 곱함 0.42 * 65536

// 반복문으로 자르고 특수문자면 앞에만 하고 넘김 , 한 만큼 cnt 세고 뺴면 교집합
// [ FR ] , RA , AN , [ NC ] , CE
// [ FR ] , RE , EN , [ NC ] , CH
// 2 / 8
// 교집합 = 같은지 확인
// 합집합 = 전체 - 교집합

 

이렇게 했을 경우 4,5,7,9,10,11,13 실패 

반례를 차장보기로 한다.

 

합집합 구하는 방식의 문제

 

import java.util.ArrayList;

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

        double jaka = 0;
        
        ArrayList<String> arr1 = new ArrayList();
        ArrayList<String> arr2 = new ArrayList();
        
        for(int i=0; i<str1.length() - 1; i++){
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr1.add(""+c1+c2);
            }
        }
        
        for(int i=0; i<str2.length() - 1; i++){
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr2.add(""+c1+c2);
            }
        }
        ArrayList<String> union = new ArrayList<>();        // 합집합
        ArrayList<String> intersection = new ArrayList<>(); // 교집합
        
        
        for(String s : arr1){
            if(arr2.remove(s)){
                intersection.add(s);
            }
            union.add(s); // 교집합 빼고 넣기
        }
        for(String s : arr2){ // 나머지 arr2값 넣기
            union.add(s);
        }
        
        int kyo = intersection.size();
        int hab = union.size();
        
        if(intersection.size() == 0){
            answer = 65536;
        } else {
            answer = (int)((double) kyo / (double)hab * 65536);
        }
        
        System.out.println(arr1);
        System.out.println(arr2);
        System.out.println("kyo : " + kyo);
        System.out.println("hab : " + hab);
        
        return answer;
    }
}

---

Solution✍

 

import java.util.ArrayList;


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

        double jaka = 0;
        
        ArrayList<String> arr1 = new ArrayList();
        ArrayList<String> arr2 = new ArrayList();
        
        for(int i=0; i<str1.length() - 1; i++){
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr1.add(""+c1+c2);
            }
        }
        
        for(int i=0; i<str2.length() - 1; i++){
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr2.add(""+c1+c2);
            }
        }
        ArrayList<String> union = new ArrayList<>();        // 합집합
        ArrayList<String> intersection = new ArrayList<>(); // 교집합
        
        for(String s : arr1){
            if(arr2.remove(s)){
                intersection.add(s);
            }
            union.add(s); // 교집합 빼고 넣기
        }
        for(String s : arr2){ // 나머지 arr2값 넣기
            union.add(s);
        }
        
        int kyo = intersection.size();
        int hab = union.size();
        
        // kyo가 0일때 안되는 이유
        // a,b가 있고 c가 있으면 
        // 교에 0들어가는 경우 , 합에 3인 경우
        // 그럼 답이 0이 나와야하는데 65536이 나와서 오류 그래서 hab == 0 을 걸어줘야 함
        // 테스트 케이스 5번이 그런경우 같은데 answer = 0;으로 보내서 검증 [ 통과 맞음 ]
        if(hab == 0){
            answer = 65536;
        } else {
            answer = (int)((double) kyo / (double)hab * 65536);
        }
        
        return answer;
    }
}

---

Review🤩

 

정렬은 필요없다.

---