알고리즘 풀이 - 프로그래머스(뉴스 클러스터링(Lv 2), 맵)

 

관련글

 

Map 관련 포스팅은 여기(1번, 2번)를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

주어진 2개의 문자열을 2개 단위 문자로 쪼개서 모두 모았을 때(중복 허용), 그 문자열의 교집합 / 합집합을 자카드 유사도라고 할 때, 그 값을 구하는 문제

 

 

2. 풀이

 

문제의 정의는 다음과 같다.

자카드 유사도 : 교집합 크기 / 합집합 크기 (두 집합의 유사도를 검사)

 

Kakao / Cacao 2개의 문자열을 각각의 집합으로 나누어보자.

 

 

우선 대소문자는 구분하지 않으므로, 위와 같이 나뉘며, 공통으로 있는 문자는 파란색으로 칠하였다.

중복이 허용되므로 전체 문자 수는 다음과 같다.

문자열	숫자
ka	2
ak	1
ao	2
ca	2
ac	1

 

이 중, 교집합 크기는 ao 1개이며, 합집합 크기는 전체 크기인 7개(ao는 공통이므로 1번만 Count)이다.

 

문제 해결 방법은 Map을 사용하여 아래와 같이 해결하였다.

① 문자열을 소문자로 치환(toLowerCase 사용)
② 2개의 Map을 구현해 주어진 2개의 문자열을 각각 단위로 쪼개 몇 번 등장했는지 저장한다.(HashMap)
③ Map 2개를 비교하여 공통으로 나온 값을 비교해 교집합에는 최소값을 더해주고, 한 쪽 맵에 합집합 계산을 위해 최대값을 갱신해준다.
④ 갱신된 나머지 Map의 모든 값을 꺼내 합집합에 추가한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.util.*;
class Solution {
    public int solution(String str1, String str2) {
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        
        // str1을 2개 단위로 쪼개 Map에 추가
        Map<String, Integer> map = new HashMap<>();
        for(int i=0; i < str1.length()-1; i++){
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i+1);
            
            if(('a' <= c1 && c1 <= 'z') && ('a' <= c2 && c2 <= 'z')){
                String str = String.valueOf(c1) + String.valueOf(c2);
                map.put(str, map.getOrDefault(str, 0) + 1);    
            }
        }
        
        // str2를 2개 단위로 쪼개 Map에 추가
        Map<String, Integer> map2 = new HashMap<>();
        for(int i=0; i < str2.length()-1; i++){
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i+1);
            
            if(('a' <= c1 && c1 <= 'z') && ('a' <= c2 && c2 <= 'z')) {
                String str = String.valueOf(c1) + String.valueOf(c2);
                map2.put(str, map2.getOrDefault(str, 0) + 1);    
            }
        }
        
        int all = 0; // 합집합
        int com = 0; // 교집합
        
        
        // 교집합 : Map / Map2에 있는 값 중 더 작은 값으로 추가
        // 합집합 : Map에 있던 값이 Map2에도 있으면 더 큰 값이 합집합에 포함, Map2에 최대값 갱신
        
        // 그외 Map2에 없는 값은 합집합으로 추가
        for(Map.Entry<String, Integer> entries : map.entrySet()){
            if(map2.containsKey(entries.getKey())){
                com += Math.min(entries.getValue(), map2.get(entries.getKey()));
                map2.put(entries.getKey(), Math.max(entries.getValue(), map2.get(entries.getKey())));
            } else {
                all += entries.getValue();
            }
        }
        
        // Map2에 있는 모든 값을 합집합에 추가
        for(Map.Entry<String, Integer> entries : map2.entrySet()){
            all += entries.getValue();
        }
        if(all == 0 && com == 0) return 65536;
        int answer = (int)((double)com / all * 65536);
        return answer;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.