Lv.2 : 뉴스 클러스터링

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 자카드 유사도를 구현하기 위해 교집합과 합집합을 구현하는 문제이다.
• 주어진 두 문자열의 파싱이 필요하다.

🔸 문제 풀이 🔸

• 두 문자열의 대소문자를 구분하지 않으므로, 대문자 혹은 소문자로 일치시킨다.
• 2문자씩 잘라서 원소로 사용하는데, 띄어쓰기나 특수문자 등 알파벳이 아닌 문자가 포함되어있으면 배제한다.
  • 여기서 주의 할 점은 알파벳이 아닌 문자들을 제거하고 2문자씩 자르는게 아닌, 먼저 자른다음 필터링 하는 순서이다.
• 중복을 허용하는 다중 집합이기 때문에 Map에 개수와 함께 저장한다.
• 교집합은 두 집합에 공통 원소를 찾고, 두 값중 최소값을 교집합 개수에 더한다.
• 합집합은 두 집합에 공통 원소의 두 값에서는 최대값을 더하고, 겹치지 않는 원소 값도 더해준다.
• 교집합 / 합집합 * 65536 을 반환한다.

---

🔸 코드 🔸

import java.util.Map;
import java.util.HashMap;

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

        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();

        for (int i = 0; i < str1.length() - 1; i++) {
            String temp = str1.substring(i, i + 2).replaceAll("[^a-zA-Z]", "");

            if (temp.length() != 2)
                continue;

            if (!map1.containsKey(temp))
                map1.put(temp, 1);
            else
                map1.put(temp, map1.get(temp) + 1);
        }

        for (int i = 0; i < str2.length() - 1; i++) {
            String temp = str2.substring(i, i + 2).replaceAll("[^a-zA-Z]", "");

            if (temp.length() != 2)
                continue;

            if (!map2.containsKey(temp))
                map2.put(temp, 1);
            else
                map2.put(temp, map2.get(temp) + 1);
        }

        if (map1.isEmpty() && map2.isEmpty())
            return 65536;

        // 교집합
        double cnt1 = 0;

        for (Map.Entry<String, Integer> entry : map1.entrySet()) {

            if (map2.containsKey(entry.getKey()) && map2.get(entry.getKey()) > 0) {
                cnt1 += Math.min(entry.getValue(), map2.get(entry.getKey()));
            }
        }

        // 합집합
        double cnt2 = 0;

        for (Map.Entry<String, Integer> entry : map1.entrySet()) {

            if (map2.containsKey(entry.getKey())) {
                cnt2 += Math.max(entry.getValue(), map2.get(entry.getKey()));
                map2.remove(entry.getKey());
            } else {
                cnt2 += entry.getValue();
            }
        }

        for (Map.Entry<String, Integer> entry : map2.entrySet()) {
            cnt2 += entry.getValue();
        }

        return (int)(cnt1 / cnt2 * 65536);
    }
}

🔸 코드 해석 🔸

• 대소문자 구분이 없으므로, 주어진 str1와 str2를 대문자로 변환해서 통일한다.
• 두 집합의 원소를 저장하기 위해 Map을 2개 만든다.
  • 각각 2문자씩 자르고 알파벳을 제외한 문자는 제거해서 길이가 2이면 집합에 포함한다.
  • 집합에 처음 넣는 원소면 값을 1, 처음이 아니면 기존값+1 로 저장한다.
  • 만약 두 집합의 원소 개수가 모두 0이라면, 합집합의 개수가 0이 나온다. 문제에서 1로 개산하라 했으므로, 1 * 65536 을 반환한다.
• 교집합은 겹치는 원소를 찾고, 저장된 두 값중 최소값을 교집합 개수에 더한다.
• 합집합은 겹치는 원소를 찾고, 저장된 두 값중 최대값을 합집합 개수에 더한다.
  • 추가로 겹치지 않은 원소의 값도 합집합 개수에 더한다.
• 교집합 / 합집합 * 65536을 반환한다.

---

🔸 end 🔸

• 카카오 문제라서 그런지 2레벨 치고는 꽤 복잡했던 것 같다. 하지만 다시보니 그냥 문자열 처리와 교집합, 합집합 구하기여서 그렇게 어렵지는 않은 것 같다.
• 처음엔 알파벳이 아닌 문자를 제거한 뒤 2문자씩 자르는 거로 이해했는데, 자른 다음 제거하는 것이었다.
  • 예제 3번에서 디버깅해줘서 알 수 있었다.
  • 예제 4번은 두 집합이 모두 0인 경우를 디버깅해줘서 또 예외처리를 할 수 있었다.
  • 예제만 맞추면 통과되도록 해둬서 2레벨인 것 같기도 하다.
• 2018 KAKAO BLIND RECRUITMENT의 5번 문제인데, 중급 난이도이고 정답률은 41.84%이다.
  • 다중 집합에서 합집합, 교집합을 구현하는게 핵심인 것 같은데, 다중 집합을 구하지 않더라도, 병합정렬을 통해 구현할 수 있다고 한다.
• 다음은 문제 해설이다.

이 문제는 자카드 유사도를 설명해주고 자카드 유사도를 직접 계산하는 프로그램을 작성하는 문제입니다. 자카드 유사도는 실무에서도 유사한 문서를 판별할 때 주로 쓰이는데요, 몰랐더라도 문제에서 자세히 설명해주기 때문에 이해하는데 어려움은 없었을 거 같습니다. 공식은 매우 간단한데요, 교집합을 합집합으로 나눈 수입니다. 다만, 이 값은 0에서 1 사이의 실수가 되는데, 여기서는 이를 다루기 쉽도록 65536을 곱한 후 소수점 아래를 버리고 정수부만 취하도록 합니다.

문제 설명은 원소의 중복을 허용하는 다중집합multiset으로 되어 있는데, 자주 접하는 자료구조가 아니고, 일부 언어에서는 기본으로 제공하는 자료구조가 아니라 어려워하는 분들이 있었습니다. 하지만 다중집합 자료구조를 쓰지 않더라도, 각 원소를 정렬된 배열에 넣은 후 병합 정렬Merge sort에서 배웠던 코드를 응용, 어렵지 않게 합집합과 교집합 함수를 직접 구현할 수도 있습니다.

다중집합의 교집합, 합집합만 잘 구해낸다면 이 문제는 어렵지 않게 풀 수 있으며, 다만 집합 A와 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으므로division by zero 따로 J(A,B) = 1로 정의합니다. 즉, 65536을 곱하면 이 경우 1 * 65536 = 65536이 정답이 됩니다. 예제 입출력에도 합집합이 공집합인 경우가 포함되어 있으므로 이 경우만 주의한다면 쉽게 풀 수 있는 문제입니다.

이 문제의 정답률은 41.84%입니다.