[프로그래머스] 뉴스 클러스터링(java)

코딩테스트 연습 - [1차] 뉴스 클러스터링 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - [1차] 뉴스 클러스터링

어떻게 생각하고 문제를 풀었는가?

교집합과 합집합을 형성하기 위해서는 집합간의 공통되는 원소를 찾을 수 있어야 합니다.

contains함수 등 탐색을 지원하는 ArrayList 자료구조를 통해 집합을 구현하고자 하였습니다.

합집합은 A + B - (A n B)로 나타낼 수 있으므로 두 집합을 합한 후 교집합을 제거함으로서 문제를 해결할 수 있을 것이라고 생각하였습니다.

코드

import java.util.*;
class Solution {
    public int solution(String str1, String str2) {
        ArrayList<String> set1 = makeSet(str1.toLowerCase());
        ArrayList<String> set2 = makeSet(str2.toLowerCase());
        ArrayList<String> union = new ArrayList<>();
        ArrayList<String> inter = new ArrayList<>();
        
        if(set1.size()==0 && set2.size()==0) return 65536;
        
        for(String e : set1){//교집합 구하기
            //if(set2.contains(e)) inter.add(e);//집합 1에서 2개, 집합 2에서 1개의 공통점이 있는경우 문제발생
            if(set2.remove(e)) inter.add(e);
        }
        union.addAll(set1);
        union.addAll(set2);
        double similar = (double)inter.size() / (union.size()==0? 1 : union.size());
        return (int)(similar*65536);
    }
    public ArrayList<String> makeSet(String str){
        ArrayList<String> set = new ArrayList<>();
        for(int i=1;i<str.length();i++){
            String e = str.substring(i-1,i+1);
            if(e.charAt(0)<97 || e.charAt(0)>122) continue;
            if(e.charAt(1)<97 || e.charAt(1)>122) continue;
            set.add(e);
        }
        return set;
    }
}

테스트를 통과한 코드입니다.

조건에 맞추어 다중집합의 원소를 ArrayList에 저장하는 makeSet함수를 작성하였고 addAll함수를 통해 두 집합에 담긴 원소들을 모두 합집합 ArrayList에 추가하였습니다.

 

교집합에 들어갈 원소를 찾는데 있어 contains함수로 공통부분을 찾고 ArrayList에 담고자 하였으나 이는 집합이 원소의 중복을 허용하기 때문에 문제가 발생하였습니다.

집합 A에 2개의 중복된 원소가 있고 집합 B에 1개의 중복된 원소가 있는 경우 A의 원소들은 모두 교집합에 추가되게 되는 것이었습니다.

이를 해결하고자 공통된 원소가 발견될 때 마다 집합 B의 원소에서 제외하는 remove함수를 사용하였습니다.

교집합 탐색 이후 집합 B의 ArrayList에는 B - (A n B)이 남아있기 때문에 합집합 ArrayList를 만드는 코드는 A + (B - A n B)로서 두 개의 addAll함수 호출로 줄일 수 있습니다.