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

프로그래머스

 

1. 문제 요약

두 문자열의 자카드 유사도를 구하시오.

 

2. 접근 방법

• 문자열이 주어질 때, 알파벳의 경우에만 원소로 사용한다는 점을 이용합니다.
  • 2글자까지만 사용하기 때문에 경우의 수는 26 * 26이 됩니다.
  • 각각의 문자열을 검사하여 26 * 26의 int[][] 배열에 담아줍니다.
• 문제를 읽어보면 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다. 라고 힌트를 주고 있습니다.
  • 이전 단계에서 생성한 배열에 힌트를 그대로 사용합니다.
• 시간 복잡도는 문자열을 배열로 변환하는 과정에서 문자열이 한글자 늘어날때마다 1번의 연산이 추가됩니다.
  • 즉, 문자열의 길이에 비례하므로 O(N)입니다.

 

3. 자바

class Solution {
    public int solution(String str1, String str2) {
        float intersection = 0;
        float union = 0;

		// 사용할 수 있는 모든 원소를 26 * 26 이중배열에 모두 담아준다.
        int[][] multiset1 = toMultiset(str1);
        int[][] multiset2 = toMultiset(str2);
        
        // 두 이중배열을 순회하면서 힌트를 그대로 사용해준다.
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                intersection += Math.min(multiset1[i][j], multiset2[i][j]);
                union += Math.max(multiset1[i][j], multiset2[i][j]);
            }
        }

		// 문제에서 제시한 조건대로 정답 가공
        return union == 0
                ? 65536
                : (int) (intersection / union * 65536);
    }

    private int[][] toMultiset(String str) {
        int[][] multiset = new int[26][26];

		// 소대문자 구분하지 않으므로 하나로 통일.
        char[] arr = str.toUpperCase().toCharArray();
        for (int i = 0; i < arr.length - 1; i++) {
            char c1 = arr[i];
            char c2 = arr[i + 1];
            // 원소로 활용할 수 있는지 검사하여 이중배열에 담아준다.
            if (Character.isAlphabetic(c1) && Character.isAlphabetic(c2)) {
                multiset[c1 - 65][c2 - 65]++;
            }
        }

        return multiset;
    }
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/17677.%E2%80%85%EF%BC%BB1%EC%B0%A8%EF%BC%BD%E2%80%85%EB%89%B4%EC%8A%A4%E2%80%85%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0%EB%A7%81/%EF%BC%BB1%EC%B0%A8%EF%BC%BD%E2%80%85%EB%89%B4%EC%8A%A4%E2%80%85%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0%EB%A7%81.java