프로그래머스 | Level 2 | 뉴스 클러스터링
Jun 27, 2024
Published byJynn
999
Programmers | Level 2 | 뉴스 클러스터링
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Hash Table
Description
여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵습니다. 이를 해결하기 위해 문자열 간의 유사도를 계산하는 자카드 유사도를 이용하여 두 문자열의 유사도를 계산하는 문제입니다.
Constraints
- 입력으로 주어지는 문자열
str1과str2의 길이는 2 이상, 1,000 이하입니다. - 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만듭니다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버립니다.
- 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시합니다.
- 입력으로 들어온 두 문자열의 자카드 유사도를 출력합니다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력합니다.
Examples
| str1 | str2 | answer |
|---|---|---|
| FRANCE | french | 16384 |
| handshake | shake hands | 65536 |
| aa1+aa2 | AAAA12 | 43690 |
| E=M*C^2 | e=m*c^2 | 65536 |
Solutions
- ⏳ TC: O(n)
- 💾 SC: O(n)
Solution.java
import java.util.*;
class Solution {
private final static String PATTERN = "[a-z]{2}";
private final static int SCALE_FACTOR = 65536;
public int solution(String str1, String str2) {
// 문자열 정돈
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();
// 집합 합산
Map<String, Integer> map1 = new HashMap<>();
for (int i = 0; i < str1.length() - 1; i++) {
String ele = str1.substring(i, i + 2);
if (ele.matches(PATTERN)) {
map1.put(ele, map1.getOrDefault(ele, 0) + 1);
}
}
Map<String, Integer> map2 = new HashMap<>();
for (int i = 0; i < str2.length() - 1; i++) {
String ele = str2.substring(i, i + 2);
if (ele.matches(PATTERN)) {
map2.put(ele, map2.getOrDefault(ele, 0) + 1);
}
}
// 공집합시 프로세스 종료
if (map1.isEmpty() && map2.isEmpty()) return SCALE_FACTOR;
// 교집합 및 합집합 원소 카운트
int inter = 0;
int union = 0;
Set<String> keys = new HashSet<>();
keys.addAll(map1.keySet());
keys.addAll(map2.keySet());
for (String key : keys) {
int count1 = map1.getOrDefault(key, 0);
int count2 = map2.getOrDefault(key, 0);
inter += Math.min(count1, count2);
union += Math.max(count1, count2);
}
// 자카드 계산
return jaccard(inter, union);
}
private int jaccard(int inter, int union) {
double jaccard = (double) inter / union;
jaccard *= SCALE_FACTOR;
return (int) jaccard;
}
}
Approaches
이 문제는 문자열 사이의 유사도를 계산하는 자카드 유사도를 활용하여 해결할 수 있습니다. 자카드 유사도는 두 집합 간의 유사도를 측정하는 방법으로, 두 집합의 교집합 크기를 합집합 크기로 나누어 계산합니다. 따라서 이 문제에서는 문자열을 두 글자씩 끊어서 다중집합을 만들고, 교집합과 합집합의 크기를 계산하는 것이 주요 과제입니다.
이를 위해 각 문자열을 두 글자씩 쪼개어 해시 테이블의 키로 사용하고, 해당 키의 빈도를 값으로 저장합니다. 예를 들어, 문자열 "FRANCE"는 다음과 같이 처리됩니다:
# 원본
"FRANCE"
# 문자열 분할
{"fr", "ra", "an", "nc", "ce"}
# 빈도수 계산
{"fr": 1, "ra": 1, "an": 1, "nc": 1, "ce": 1}
해시 테이블을 사용하면 두 글자 쌍의 빈도를 효율적으로 관리할 수 있습니다. 이렇게 생성된 두 해시 테이블을 비교하여 각 두 글자 쌍의 빈도를 비교합니다. 교집합은 동일한 키를 가진 원소 중 작은 빈도 값을 합산하고, 합집합은 큰 빈도 값을 합산하여 계산할 수 있습니다.
- 문자열 전처리:
- 주어진 문자열을 소문자로 변환하여 대소문자 차이를 무시합니다.
- 두 글자씩 끊어서 영문자 쌍만 유효한 원소로 다중집합을 만듭니다.
- 해시맵을 이용한 빈도 카운트:
- 각 문자열의 다중집합 원소를 해시맵에 저장합니다. 해시맵의 키는 두 글자 쌍, 값은 해당 쌍의 빈도입니다.
- 두 문자열 각각에 대해 해시맵을 생성하여 원소의 빈도를 카운트합니다.
- 교집합 및 합집합 계산:
- 두 해시맵의 키를 합친 후, 각 키에 대해 두 해시맵에서의 최소값이 교집합, 최대값이 합집합의 크기가 됩니다.
- 자카드 유사도 계산:
- 교집합 크기를 합집합 크기로 나누어 자카드 유사도를 계산합니다.
- 결과에 65536을 곱하고 소수점을 버려 정수부만 반환합니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(n)입니다. 이는 주어진 문제를 효율적으로 해결하는 데 충분합니다.
Attempts
처음에는 두 문자열을 두 글자씩 쪼개어 다중집합 원소 배열을 생성하고, 이를 활용하여 자카드 유사도를 계산하려고 했습니다. 이를 위해 각 다중집합의 원소를 해시맵에 저장하고, 교집합과 합집합을 계산하는 방식으로 접근했습니다. 이를 구현한 코드는 아래와 같습니다:
Solution.java
import java.util.*;
class Solution {
private static final String PATTERN = "^[a-zA-Z]{2}$";
private static final int SCAILING_FACTOR = 65536;
public int solution(String str1, String str2) {
// 다중집합 원소 배열 생성: 두 문자, 알파벳 조합
List<String> arr1 = new ArrayList<>();
List<String> arr2 = new ArrayList<>();
Map<String, Integer> map1 = new HashMap<>();
Map<String, Integer> map2 = new HashMap<>();
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();
for (int i = 0; i < str1.length() - 1; i++) {
String ele = str1.substring(i, i + 2);
if (ele.matches(PATTERN)) {
arr1.add(ele);
map1.put(ele, map1.getOrDefault(ele, 0) + 1);
}
}
for (int i = 0; i < str2.length() - 1; i++) {
String ele = str2.substring(i, i + 2);
if (ele.matches(PATTERN)) arr2.add(ele);
map2.put(ele, map2.getOrDefault(ele, 0) + 1);
}
if (arr1.isEmpty() && arr2.isEmpty()) return SCAILING_FACTOR;
// 교집합 계산
List<String> inter = new ArrayList<>();
for (Map.Entry<String, Integer> entry : map1.entrySet()) {
String key = entry.getKey();
Integer count1 = entry.getValue();
if (map2.containsKey(key)) {
Integer count2 = map2.get(key);
for (int i = 0; i < Math.min(count1, count2); i++) {
inter.add(key);
}
}
}
// 합집합 계산
List<String> union = new ArrayList<>();
for (String ele : inter) {
arr1.remove(ele);
arr2.remove(ele);
union.add(ele);
}
union.addAll(arr1);
union.addAll(arr2);
// 자카드 유사도 계산
return jaccard(inter.size(), union.size());
}
private int jaccard(double inter, double union) {
if (inter == 0 || union == 0) return SCAILING_FACTOR;
return (int) Math.floor(inter / union * SCAILING_FACTOR);
}
}
이 방식은 다음과 같은 절차로 이루어집니다:
- 두 문자열을 소문자로 변환하고, 각 문자열을 두 글자씩 쪼개어 유효한 두 글자 쌍만을 다중집합 원소 배열에 추가합니다.
- 각 다중집합 원소 배열을 해시맵에 저장하여 각 원소의 빈도를 카운트합니다.
- 두 해시맵을 비교하여 교집합 원소를 계산합니다. 동일한 키를 가진 원소 중 작은 빈도 값을 교집합에 추가합니다.
- 교집합을 기반으로 원래 배열에서 해당 원소를 제거한 후, 나머지 원소들을 합집합에 추가합니다.
- 교집합 크기를 합집합 크기로 나누어 자카드 유사도를 계산하고, 결과에 65536을 곱하여 반환합니다.
이 접근 방식에서 두 가지 주요 실수가 있었습니다.
- 첫째, 교집합이나 합집합의 크기가 0일 경우, 결과가 0이 되어야 하는데 이를 1로 처리했습니다. 공집합을 1로 처리하여 잘못된 결과를 초래했습니다.
Solution.java
private int jaccard(double inter, double union) {
if (inter == 0 || union == 0) return SCAILING_FACTOR; // 🐛
return (int) Math.floor(inter / union * SCAILING_FACTOR);
}
- 둘째, 문제 설명에 따라 빈도 수 계산으로 비교할 수 있었는데, 불필요하게 문자열을 직접 비교했습니다. 이러한 판단으로 인해 코드는 너무 복잡하고 비효율적으로 작성되었습니다.
이 두 가지 실수로 인해 문제를 해결하는 데 어려움을 겪었고, 최종적으로 더 효율적이고 정확한 알고리즘으로 전환하게 되었습니다.
- Algorithm
- Hash Table