[프로그래머스] [자바] [카카오] 뉴스 클러스터링

https://programmers.co.kr/learn/courses/30/lessons/17677?language=java 

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

문제 접근

쓴 자료형 

 

Map

단어들의 집합을 표현할 때 중복되는 것도 고려해야하는 문제를 어떻게 효율적으로 해결할까 고민하던 중 맵 자료형을 쓰면 좋을 것 같아서 사용하였다. 단순히 리스트를 사용하기에는 시간 복잡도 면에서 손해보는 것이 있기 때문에 Map 자료형이 더 탁월한 것 같다.

 

Set

이 문제의 핵심 자료형이다. 교집합, 합집합 키워드를 보면 바로 set 자료형을 생각해야 한다. 그런 것을 다루기에 최적화된 자료형이므로 기억하자.

 

import java.util.*;

class Solution {
   
    public int solution(String str1, String str2) {
        Aggregation aggregation = new Aggregation(str1,str2);
        return aggregation.getValue();
    }

    public static class Aggregation {
        private static final int DEFAULT = 65536;
        private final String leftString;
        private final String rightString;
        private final Map<String,Integer> left;
        private final Map<String,Integer> right;
        private Set<String> leftKeys;
        private Set<String> rightKeys;
        private final Set<String> hap;
        private int parent;
        private int children;
        public Aggregation(String leftString, String rightString) {
            this.leftString = leftString;
            this.rightString = rightString;
            left = new HashMap<>();
            right = new HashMap<>();
            hap = new HashSet<>();
        }
        
        public int getValue() {
            mappingChunkWords();
            countParent();
            countChildren();
            if (parent==0)
                return DEFAULT;
            else{
                double answer = children/(double)parent;
                return (int)(DEFAULT*answer);
            }
        }
        
        private void countParent() {
            for (String key: hap) {
                parent += Math.max(left.getOrDefault(key, 0), right.getOrDefault(key, 0));
            }
        }
        
        private void countChildren() {
            leftKeys.retainAll(rightKeys);
            for (String key: leftKeys) {
                children += Math.min(left.getOrDefault(key,0),right.getOrDefault(key,0));
            }
        }
        
        private void mappingChunkWords() {
            makeCombinations(leftString,left);
            makeCombinations(rightString,right);
            leftKeys = left.keySet();
            rightKeys = right.keySet();
            hap.addAll(leftKeys);
            hap.addAll(rightKeys);
        }
        
        private void makeCombinations(String str, Map<String,Integer> basket) {
            for (int i = 0; i < str.length() - 1; i++) {
                char first = str.charAt(i);
                char second = str.charAt(i+1);
                if (isLowerAlpha(first) || isUpperAlpha(first)) {
                    if (isLowerAlpha(second) || isUpperAlpha(second)) {
                        char[] chunk = {first, second};
                        String word = new String(chunk);
                        word = word.toUpperCase(Locale.ROOT);
                        basket.put(word, basket.getOrDefault(word, 0) + 1);
                    }
                }
            }
        }
        
        private  boolean isLowerAlpha(char c) {
            return c >= 'a' && c <= 'z';
        }

        private  boolean isUpperAlpha(char c) {
            return c >= 'A' && c <= 'Z';
        }
    }
}

makeCombinations

단어들의 규칙을 고려하여 뽑아야 한다.

1. 소문자, 대문자 고려하지 않는다.
2. 반드시 알파벳이어야 한다.
3. 단어들의 중복을 고려해야 한다.

isLowerAlpha

소문자 체크

 

isUpperAlpha

대문자 체크

 

mappingChunkWords

 

makeCombinations() 메소드를 불러와 두 단어의 Map 자료형에 대한 데이터를 넣어준다. 그리고 그에 대한 key들을 따로 저장하고 합집합을 위한 set에 두 개의 키들을 넣어준다.

 

countParent

분모에 해당하는 합집합 갯수를 카운팅한다.

 

countChildren

분자에 해당하는 교집합 갯수를 카운팅한다.

 

getValue

값을 내는 기준에 맞게 구한다.

1. 분모가 0이면 DEFAULT 값으로 반환
2. DEFAULT * ( 교집합/합집합) [소수점 버림]