(1차) 뉴스 클러스터링

작성일: 2024-11-11

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17677

접근 방식

각각의 문자열을 통합하기 위해, 모두 대문자로 변환한다.

이후 2문자씩 끊어서 모두 대문자에 해당하는지 확인하고, 해당 한다면 문자열을 만들어서 리스트에 추가한다.

그렇게 만들어진 두 개의 리스트를 비교하며, 교집합과 합집합을 구한다.

잘못된 접근

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        List<String> a = new ArrayList<>();
        List<String> b = new ArrayList<>();
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<str1.length()-1; i++){
            int tmp1 = str1.charAt(i) - 'A';
            int tmp2 = str1.charAt(i+1) - 'A';
            if(tmp1>=0 && tmp1<=25 && tmp2>=0 && tmp2<=25){
                sb.append(str1.charAt(i)).append(str1.charAt(i+1));
                a.add(sb.toString());
                sb.setLength(0);
            }
        }
        sb.setLength(0);
        for(int i=0; i<str2.length()-1; i++){
            int tmp1 = str2.charAt(i) - 'A';
            int tmp2 = str2.charAt(i+1) - 'A';
            if(tmp1>=0 && tmp1<=25 && tmp2>=0 && tmp2<=25){
                sb.append(str2.charAt(i)).append(str2.charAt(i+1));
                b.add(sb.toString());
                sb.setLength(0);
            }
        }
        if(a.isEmpty() && b.isEmpty()) return 65536;
        int commonCnt = compare(a, b); // 교집합
        int sumCnt = a.size()+b.size()-commonCnt; // 합집합
        double answer = (double)commonCnt/(double)sumCnt;
        return (int)(answer*65536);
    }

    int compare(List<String> a, List<String> b){
        int cnt = 0;
        for(int i=0; i<a.size(); i++){
            if(b.contains(a.get(i))) cnt++;
        }

        return cnt;
    }
}

위 방식에는 문제가 있다. 바로 한 개만 가지고 있더라고 가지고 있다고 생각하여 체크한다는 것.

예를 들어, A=(11, 12, 11, 11), B=(11, 11, 13) 과 같이 두 개의 집합이 있다고 했을 때

교집합은 11, 11 두 개만 존재해야 한다. 하지만 현재 로직에서는 세 번째 11을 체크할 때 B 집합에 11이 존재하기 때문에 3번째 11도 교집합에 추가하여
최종 교집합은 (11, 11, 11)이 된다. 따라서 교집합에 추가하면 해당 원소를 제거해야 중복 체크가 발생하지 않는다.

b.remove(a.get(i));

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        List<String> a = new ArrayList<>();
        List<String> b = new ArrayList<>();
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<str1.length()-1; i++){
            int tmp1 = str1.charAt(i) - 'A';
            int tmp2 = str1.charAt(i+1) - 'A';
            if(tmp1>=0 && tmp1<=25 && tmp2>=0 && tmp2<=25){
                sb.append(str1.charAt(i)).append(str1.charAt(i+1));
                a.add(sb.toString());
                sb.setLength(0);
            }
        }
        sb.setLength(0);
        for(int i=0; i<str2.length()-1; i++){
            int tmp1 = str2.charAt(i) - 'A';
            int tmp2 = str2.charAt(i+1) - 'A';
            if(tmp1>=0 && tmp1<=25 && tmp2>=0 && tmp2<=25){
                sb.append(str2.charAt(i)).append(str2.charAt(i+1));
                b.add(sb.toString());
                sb.setLength(0);
            }
        }
        int answer = 65536;
        if(a.isEmpty() && b.isEmpty()) return answer;
        int sumCnt = a.size()+b.size(); // 합집합
        int commonCnt = a.size()>b.size() ? compare(b,a) :compare(a, b); // 교집합
        sumCnt-=commonCnt;
        answer = (int)(((double)commonCnt/(double)sumCnt)*65536);
        return answer;
    }

    int compare(List<String> a, List<String> b){
        int cnt = 0;
        for(int i=0; i<a.size(); i++){
            if(b.contains(a.get(i))) {
                b.remove(a.get(i));
                cnt++;
            }
        }

        return cnt;
    }
}

다른 접근 방식

없음.

알게 된 점

없음.