[프로그래머스] 17677. 뉴스 클러스터링

문제 링크

[프로그래머스] 17677. 뉴스 클러스터링

풀이 과정

중복만 없다면, Set 자료구조의 addAll, retainAll 메소드를 사용해 합집합, 교집합을 표현할 수 있어 쉽게 풀릴 문제였다고 생각되었지만, 문제가 다중 집합(또는 중복 집합)을 허용하기 때문에 이를 어떻게 구현할 것인가에 대한 생각을 많이 한 문제였습니다.

중복 집합의 합집합 및 교집합은 ArrayList 네 개를 사용해서 구현할 수 있었습니다.

List<String> list1 = new ArrayList<>();
List<String> list2 = new ArrayList<>();
List<String> intersection = new ArrayList<>();
List<String> union = new ArrayList<>();

list1을 주축으로 돌며, 요소가 list2에도 속해있다면 요소를 제거하고, 해당 요소를 합집합 뿐만 아니라 교집합에도 추가시켜줍니다. list2에 남아있는 요소는 합집합에 따로 추가해줍니다.

for (String s : list1) {
    if (list2.remove(s))
        intersection.add(s);

    union.add(s);
}

for (String s : list2)
    union.add(s);

코드

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

public class Main {
    public static int solution(String str1, String str2) {
        List<String> list1 = new ArrayList<>();
        List<String> list2 = new ArrayList<>();
        List<String> intersection = new ArrayList<>();
        List<String> union = new ArrayList<>();

        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();

        for (int i = 0; i < str1.length() - 1; i++) {
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i + 1);

            if (c1 >= 'A' && c1 <= 'Z' && c2 >= 'A' && c2 <= 'Z') {
                list1.add(c1 + "" + c2);
            }
        }

        for (int i = 0; i < str2.length() - 1; i++) {
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i + 1);

            if (c1 >= 'A' && c1 <= 'Z' && c2 >= 'A' && c2 <= 'Z') {
                list2.add(c1 + "" + c2);
            }
        }

        for (String s : list1) {
            if (list2.remove(s))
                intersection.add(s);

            union.add(s);
        }

        for (String s : list2)
            union.add(s);

        double jakard = intersection.size() == 0 && union.size() == 0 ? 1 : (double) intersection.size() / union.size();

        return (int) (jakard * 65536);
    }

    public static void main(String[] args) {
//        String str1 = "FRANCE";
//        String str2 = "french";

//        String str1 = "handshake";
//        String str2 = "shake hands";

//        String str1 = "aa1+aa2";
//        String str2 = "AAAA12";

        String str1 = "E=M*C^2";
        String str2 = "e=m*c^2";

        solution(str1, str2);
    }
}