[PG] 카카오 블라인드 1차 테스트 > 뉴스 클러스터링

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

접근 방법

먼저 문제에 대한 이해가 필요했었다.

제일 어려운 부분은 "자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자." 이 부분이 되었을 것 같다.

str1 = "abccc" str2="ccdfegg" 가 된다면 합집합은 "abcccdfegg" 가 된다는 걸 놓치면 안된다.

나는 먼저 HashMap을 사용하기로 하였다.

그 이유는 str1과 str2에 대한 부분 집합을 먼저 HashMap에 넣어주게 되면 나중에 검사하게 될 때 get(Key)로 포함되어 있는 집합인지 확인하는 게 빠르게 때문이다.

주의 사항

Need Know

1. 문자열
2. HashMap

전체 코드 ( Java )

import java.util.*;
class Solution {
    static final int NUMBER = 65536;
    public int solution(String str1, String str2) {
        double answer = 0;
        StringBuilder sb = new StringBuilder(str1.toLowerCase());
        StringBuilder sb2 = new StringBuilder(str2.toLowerCase());
        HashMap<String,Pointer> hash = new HashMap<>();
        int comm = 0;
        int other = 0;
        for(int i=0; i<sb.length(); i++){
            if(sb.length() != i+1){
                String ss = sb.substring(i,i+2);
                if(ss.matches("[a-z]+")){
                    if(hash.containsKey(ss)){
                        hash.put(ss, new Pointer(hash.get(ss).cnt+1, false));
                    }else{
                        hash.put(ss,new Pointer(1, false));
                    }
                }
            }
        }
        HashMap<String, Pointer> hash2 = new HashMap<>();
        for(int i=0; i<sb2.length(); i++){
            if(sb2.length() != i+1){
                String ss = sb2.substring(i,i+2);
                if(ss.matches("[a-z]+")){
                    if(hash2.containsKey(ss)){
                        hash2.put(ss, new Pointer(hash2.get(ss).cnt+1, false));
                    }else{
                        hash2.put(ss, new Pointer(1, false));
                    }
                }
            }
        }
        for (Map.Entry<String, Pointer> entry : hash.entrySet()) {
            if(hash2.containsKey(entry.getKey())){
                comm += Math.min(hash2.get(entry.getKey()).cnt, hash.get(entry.getKey()).cnt);
                other += Math.max(hash2.get(entry.getKey()).cnt, hash.get(entry.getKey()).cnt);
                hash2.get(entry.getKey()).check = true;
            }else{
                other += entry.getValue().cnt;
            }
        }
        for (Map.Entry<String, Pointer> entry : hash2.entrySet()) {
            if(!entry.getValue().check){
                other += entry.getValue().cnt;
            }
        }
        if(other == 0 && comm == 0){
            return 1 * NUMBER;
        }
        return (int)(((float)comm/other)*NUMBER);
    }
}
class Pointer{
    boolean check;
    int cnt;
    public Pointer(int cnt, boolean check){
        this.check = check;
        this.cnt = cnt;
    }
}