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

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

프로그래머스

 

1. 서론

 

그냥 구현하는 문제인데 구현 자체는 어렵지 않은데 이 문제에 나오는 '자카드 유사도'라는 개념 자체가 어렵다.

일반적인 합집합, 교집합 개념만 사용하면 4, 7, 9, 10, 11 테케가 무조건 틀린다. 문자를 꼼꼼히 안 읽은 죄.

 

 

 

반응형

 

 

 

2. 문제 풀이

 

자카드 유사도란...?

쉽게 말하자면 A, B라는 집합이 있다고 가정하자. 그렇다면 보통의 합집합이란? A + B - 교집합 일 것이다.

교집합 역시 마찬가지다. A, B 중 같은 값이 존재한다면 그것이 교집합이다.

그런데 이 문제는 중복을 허용한다. 그렇기 때문에 그에 대한 규칙이 존재한다.

교집합의 경우 각 집합에 중복되는 값이 여러 개이면 그 개수를 계산할 때 그 수가 적은 집합 쪽의 수대로 합치고,

합집합의 경우에는 반대로 그 수가 큰 집합 쪽의 수대로 합친다. 

 

 

 

 

반응형

 

 

 

 

 

예시를 통해 문제를 이해해보자

 

ex)

 

A = {AB, BA, AB}

B = {BA, AB, BA}

 

case 1) 일반적인 경우

 

교집합: AB, BA

합집합: AB, BA

 

case 2) 중복 허용 + 추가 조건을 적용하는 경우

 

교집합: AB, BA 

합집합: AB, AB, BA, BA

 

A집합은 AB 2, BA 1

B집합은 AB 1, BA 2

 

그렇기 때문에 교집합에서는 각 집합에서 작은 수를, 합집합에서는 큰 수를 택해 합친 것이다.

 

tc 4, 7, 9, 10, 11 만 틀린다면 이 케이스에 걸린 것이다. 나머지 케이스는 일반적인 교집합, 합집합(+중복 허용)까지만 해도 풀린다.

이렇게 구한 교집합의 개수 / 합집합의 개수 * 65536 하면 문제는 풀린다.

 

나는 HashMap을 사용해 중복을 관리했다. 자세한 내용은 코드를 보면서 설명 ㄱㄱ

 

 

 

반응형

 

 

 

3. 코드 설명

 

import java.util.*;

class Solution {
    
    public int solution(String str1, String str2) {
        int answer = 0;
        
        str1 = str1.toUpperCase();
        HashMap<String, Integer> list1 = makeList(str1);
        str2 = str2.toUpperCase();
        HashMap<String, Integer> list2 = makeList(str2);
        
        HashMap<String, Integer> total = new HashMap<>();
        total.putAll(list2);
        
        int s1 = 0;
        for (Map.Entry<String, Integer> i : list1.entrySet()) {
            int f = 0;
             for (Map.Entry<String, Integer> j : list2.entrySet()) {
                if (i.getKey().equals(j.getKey())) {
                    total.put(j.getKey(), Math.max(i.getValue(), j.getValue()));
                    if (i.getValue() > 1 && j.getValue() > 1)
                        s1 += Math.min(i.getValue(), j.getValue());
                    else
                        s1++;
                    f = 1;
                    break;
                }
             }
            if (f == 0)
                total.put(i.getKey(), i.getValue());
        }
        
        int s2 = 0;
        for (Map.Entry<String, Integer> i : total.entrySet())
            s2 += i.getValue();
        
        if (s2 == 0)
            answer = 65536;
        else 
           answer = (int) ((double)s1/s2 * 65536);

        return answer;
    }
    
    public HashMap<String, Integer> makeList(String s) {
        HashMap<String, Integer> list = new HashMap<>();
        
        for (int i = 0; i < s.length() - 1; i++) {
            String t = s.substring(i, i + 2);
            
            int f = 0;
            for (int j = 0; j < t.length(); j++) {
                if (!Character.isAlphabetic(t.charAt(j))) {
                    f = 1;
                    break;
                }
            }
            if (f == 0) {
                if (list.containsKey(t))
                    list.put(t, (int)list.get(t) + 1);
                else
                    list.put(t, 1);
            }
        }
        
        return list;
    }
}

 

문제에서 대소문자 구분을 안 한다고 했기 때문에 일괄로 toUpperCase 사용해 대문자 처리하고 시작했다.

알파벳이 아니면 집합의 조건에 포함되지 않기 때문에 Character.isAlphabetic를 사용해 배열을 만들어주며 처리해 줬다.

 

그리고 교집합, 합집합을 만들기 위해 HashMap을 사용했다. 

배열을 만들면서도 중복이 있으면 그 수를 체크했고, 빈 배열에 한 집합을 넣고 남은 집합과 비교하며 값이 중복인 경우 배열에 큰 값이 들어가게 해 줬고, 동시에 교집합도 cnt 하기 위해 작은 값의 합을 구했다.

 

그리고 0으로 나누는 에러를 막기 위해 문제에서는 공집합인 경우 1로 계산하게 해 줘서 조건을 처리해 줬다.

그리고 나누기는 실수형으로 해야 하지만 마지막에 65536을 곱하는 결괏값은 정수로 나와야 했기 때문에 타입캐스팅을 해줬다.