[201216] 뉴스 클러스터링 - 2018 KAKAO BLIND RECRUITMENT

0. 문제 유형 : 적절한 자료구조 활용, 예외 처리

1. 문제 이해

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

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

(1) 주요 요구사항

: 주어진 두 string(str1, str2)의 (자카드 유사도*65536)의 정수부 구하기

자카드 유사도 J(A, B) = (A와 B의 교집합 크기) / (A와 B의 합집합 크기)

 

- 다중집합 확장 : 중복되는 원소 각자 처리

ex> A= {1,1,2,2,3}, B = {1,2,2,4,5} → A∩B = {1,2,2}, AUB = {1,1,2,2,3,4,5}

즉, 교집합은 각 원소 종류 개수의 최솟값을, 합집합은 각 원소 종류 개수의 최댓값을 가져온다.

	1	2	3	4	5
n(A∩B)	min(1,2)	min(2,2)	min(1,0)	min(0,1)	min(0,1)
n(AUB)	max(1,2)	max(2,2)	max(1,0)	max(0,1)	max(0,1)

 

- 문자열에서의 유사도 계산

: 두 글자씩 끊어서 다중집합 형성

ex> "FRANCE" → {"FR", "RA", "AN", "NC", "CE"}

 

(2) 제한 사항

- st1과 str2의 길이 : 2이상 1,000이하

- 다중집합의 원소 : 영문자만 유효 (숫자, 특수 문자 쌍은 버림)

- 대문자, 소문자 차이 무시 → toLowerCase OR toUpperCase로 처리

- 교집합, 합집합이 모두 0인 경우 J(A,B) = 1로 처리

 

 

 

2. 전략

(1) makeMap 메소드 : 다중집합 만들기

- 각 string을 HashMap에 <원소, 개수> 형태로 넣기

- 제한 사항 고려 : target이 영문자인지 한 글자씩(character) 확인(isAlphabetic) + 맞다면 toLowerCase로 key 설정

if(Character.isAlphabetic(target1) && Character.isAlphabetic(target2)){
    String key = str.substring(i, i+2).toLowerCase();
    ...
}

- 단, 유효한 key에 대해 공통의 HashSet에 담아 원소의 모든 종류를 담은 자료구조 하나 형성

 

(2) 자카드 유사도 구하기

- (1)에서 구한 HashSet의 모든 원소에 대하여 진행

- a, b = map1, map2에서 각각 key에 해당하는 value 값. 만약 존재하지 않는다면 0으로

- n(A∩B) = Math.min(a,b) / n(AUB) = Math.max(a, b)

- 제한 사항 고려 : n(A∩B)와 n(AUB)이 모두 0이면 1로 처리!! -- 내가 실수했던 부분 

 

 

 

3. 참고사항

(1) 영문자인지 확인하는 방법

- Character의 메소드 활용

Character.isAlphabetic(target1)

- ACSII 코드 활용

if((target1 >= 'A' && target1 <= 'Z') || (target1 >= 'a' && target1 <= 'z'))

int target2 = (int)target1
if((target2 >= 65 && target2 <= 90) || (target2 >= 97 && target2 <= 122))

** A : 65, Z : 90, a : 97, z : 122 정도는 외워두자

 

- regex pattern matching 활용 : String으로 확인할 수 있다는 장점

String target = str1.substring(i, i+2).toLowerCase()
if(target.matches("^[a-z]+$"))

 

(2) 나눗셈 

- 정수끼리 나누면 결과는 항상 정수만 나옴

→ float나 double로 casting하여 계산하는 것을 잊지 말자!!

 

 

 

4. 코드

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        HashMap<String, Integer> map1 = new HashMap<>();
        HashMap<String, Integer> map2 = new HashMap<>();
        HashSet<String> set = new HashSet<>();
        int answer = 0;
        makeMap(str1, map1, set);
        makeMap(str2, map2, set);
        Iterator<String> itr = set.iterator();
        int num1 = 0; int num2 = 0;
        while(itr.hasNext()){
            String target = itr.next();
            int a = (map1.containsKey(target)) ? map1.get(target) : 0;
            int b = (map2.containsKey(target)) ? map2.get(target) : 0;
            num1 += Math.min(a, b);
            num2 += Math.max(a, b);
        }
        answer = (num1 == 0 && num2 == 0) ? 65536 : (int)((float)num1 / (float)num2 * 65536);
        return answer;
    }

    public void makeMap(String str, HashMap<String, Integer> map, HashSet<String> set){
        for(int i = 0; i < str.length()-1; i++){
            char target1 = str.charAt(i);
            char target2 = str.charAt(i+1);
            if(Character.isAlphabetic(target1) && Character.isAlphabetic(target2)){
                String key = str.substring(i, i+2).toLowerCase();
                if(!map.containsKey(key))  map.put(key, 1);
                else    map.replace(key, map.get(key) + 1);
                set.add(key);
            }
        }
    }
}