프로그래머스 뉴스 클러스터링 풀이

프로그래머스 뉴스 클러스터링

문제 정의

두 문자열에서 연속된 2글자씩 끊어 만든 다중집합을 구성하고, 두 다중집합의 자카드 유사도 J(A, B) = 교집합(A,B) / 합집합(A,B) 를 계산해
65536을 곱해 소수점 아래를 버린 값을 구해야 한다.

• 알파벳만 유효(숫자/특수문자 포함 쌍은 제외)
• 대소문자 구분 없음(모두 소문자로 처리)
• 다중집합(원소 중복 허용) 기준의 교집합/합집합 계산
• 두 집합 모두 공집합이면 유사도 1로 간주, 65536 반환

접근 방법

• 문자열을 순회하며 2글자 쌍을 만들고, 둘 다 알파벳인 경우만 선택

• 소문자로 변환하여 정규화 : tolower() 사용

• 다중집합 구현은 2차원 카운팅 배열 사용: 알파벳 26×26 (a~z)

  • count1[a][b], count2[a][b]

• 교집합 크기: 각 키에 대해 min(count1, count2)의 합

• 합집합 크기: 각 키에 대해 max(count1, count2)의 합
  - 예시의 힌트를 활용했다!
  
  개꿀

• 합집합이 0이면 65536, 아니면 floor((inter/union) * 65536) 반환

구현 코드 (C++)

#include <bits/stdc++.h>

// 어 문자열 문제? 
// 유사도를 구하는데 2개씩 비교 (교집합) / (합집합)
// 집합 A와 집합 B가 모두 공집합일 경우 -> 1

// 확장하니 원소의 중복을 허용하는 다중집합
// (교집합-중복x) / (합집합-중복o)
// 알파벳 + 빈도 수 -> 2차원 <키(a,b), 나오는 빈도> 배열 활용
using namespace std;


int solution(string str1, string str2) {
    int answer = 0;
    
    int ch_map1[26][26];
    int ch_map2[26][26];
    
    fill(&ch_map1[0][0], &ch_map1[0][0]+26 * 26, 0);
    fill(&ch_map2[0][0], &ch_map2[0][0]+26 * 26, 0);
    //알바벳 first, second 에 저장되는 cnt -> 0으로 초기화
    
    for(int i = 0; i < str1.size()-1; i++){
        char a = tolower(str1[i]);
        char b = tolower(str1[i+1]);
        if (isalpha(a) && isalpha(b)) {
            ch_map1[a - 'a'][b - 'a']++;
        }
    }
    for(int i = 0; i < str2.size()-1; i++){
        char a = tolower(str2[i]);
        char b = tolower(str2[i+1]);
        if (isalpha(a) && isalpha(b)) {
            ch_map2[a - 'a'][b - 'a']++;
        }
    }
    
    
    
    int interCnt = 0; //교집합
    int unionCnt = 0; //합집합
    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            interCnt += min(ch_map1[i][j], ch_map2[i][j]); 
            //설명에서 다중집합 확장한 방법
            unionCnt += max(ch_map1[i][j], ch_map2[i][j]);
        }
    }
    
    if (unionCnt == 0) return 65536; //공집합이면 유사도 1
    
    //자카드 유사도 계산
    answer = floor( (interCnt*1.0 / unionCnt) * 65536);//소수점 버림
    
    return answer;
}

핵심 포인트

1. 정규화: 대소문자 무시 -> 모두 소문자 변환
2. 유효 문자 필터링: 2글자 모두 알파벳일 때만 선택하기
3. 다중집합 계산: 교집합은 min, 합집합은 max의 합으로 구현 : 설명 내에 답이 있었다.
4. 엣지 케이스: 합집합이 0이면 65536 반환
5. 상수 크기 맵: 26×26 카운팅 배열로 빠르게 처리 (메모리/속도 유리)

시간 복잡도

• 문자열 전처리: O(|str1| + |str2|)
• 교집합/합집합 계산: O(26×26) = O(1)
• 전체: O(N)

학습 포인트

• 다중집합 교집합/합집합을 빈도 맵으로 구현하는 패턴 이해
• 문자열 전처리와 유효성 검사(isalpha, tolower) 순서 중요
• 자카드 유사도 정의 및 엣지 케이스 처리(공집합)