뉴스 클러스터링
문제정의
두 문자열을 두글자씩 쪼개어(이 때 영문외의 다른 문자가 끼어있으면 버린다.) 자카드 유사도를 구하는 문제이다. 아래 링크에 원문을 붙였으니 참고 바란다.
문제 링크
문제풀이
전체 코드는 다음과 같다. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98package level2;
import java.util.HashMap;
import java.util.Iterator;
public class NewsClustering {
//프로그래머스 문제풀이 Level2 뉴스 클러스터링
public static void main(String[] args) {
String str1 = "aa1+aa2";
String str2 = "AAAA12";
char[] arr1 = str1.toCharArray();
char[] arr2 = str2.toCharArray();
HashMap<String, Integer> a = new HashMap<>();
HashMap<String, Integer> b = new HashMap<>();
HashMap<String, Integer> inter = new HashMap<>();
HashMap<String, Integer> union = new HashMap<>();
for(int i = 0; i < arr1.length-1; i++)
{
if((arr1[i] < 'A' || arr1[i] > 'Z') && (arr1[i] < 'a' || arr1[i] > 'z'))
continue;
if((arr1[i+1] < 'A' || arr1[i+1] > 'Z') && (arr1[i+1] < 'a' || arr1[i+1] > 'z'))
continue;
StringBuilder buff = new StringBuilder();
buff.append(arr1[i]);
buff.append(arr1[i+1]);
String key = buff.toString().toLowerCase();
a.put(key, a.getOrDefault(key, 0)+1);
}
for(int i = 0; i < arr2.length-1; i++)
{
if((arr2[i] < 'A' || arr2[i] > 'Z') && (arr2[i] < 'a' || arr2[i] > 'z'))
continue;
if((arr2[i+1] < 'A' || arr2[i+1] > 'Z') && (arr2[i+1] < 'a' || arr2[i+1] > 'z'))
continue;
StringBuilder buff = new StringBuilder();
buff.append(arr2[i]);
buff.append(arr2[i+1]);
String key = buff.toString().toLowerCase();
b.put(key, b.getOrDefault(key, 0)+1);
}
Iterator<String> keys = a.keySet().iterator();
while(keys.hasNext())
{
String key = keys.next();
int b_value = b.getOrDefault(key, 0);
if(b_value != 0)
inter.put(key, Math.min(b_value, a.get(key)));
union.put(key, a.get(key));
}
Iterator<String> b_keys = b.keySet().iterator();
while(b_keys.hasNext())
{
String key = b_keys.next();
union.put(key, Math.max(b.get(key), union.getOrDefault(key, 0)));
}
Iterator<String> inter_keys = inter.keySet().iterator();
Iterator<String> union_keys = union.keySet().iterator();
double inter_size = 0, union_size = 1;
while(inter_keys.hasNext())
inter_size += inter.get(inter_keys.next());
while(union_keys.hasNext())
union_size += union.get(union_keys.next());
union_size--;
double similarity = inter_size/union_size;
similarity *= 65536;
int answer = (int)Math.floor(similarity);
if(inter.size() == 0)
answer = 65536;
System.out.println(answer);
}
}
과정을 나누니 어렵지 않다. 1,2번 코드는 같은 논리로 동작하므로 하나만 떼어서 보자.
1 | for(int i = 0; i < arr1.length-1; i++) |
필자는 hashmap을 사용해서 문제를 풀었다. 일단 arr1에 문자열을 쪼개어 문자 배열로 만든 다음 두글자씩 보면서 영어가 아닌 것이 있으면 map에 추가되지 않도록 continue를 사용했다. 만약 두 문자다 영어라면 버퍼에 문자들을 넣어주고 전부 소문자로 바꾸어주었다. 이유는 대문자 소문자를 구별하지 않는다고 문제에 나와있기 때문이다. 이후 맵에 문자를 key값으로 하고 값은 만약 이미 값이 있다면 기존값에 +1을 없다면 1을 삽입하도록 한다.
1 | Iterator<String> keys = a.keySet().iterator(); |
1,2번 과정이 끝났으니 이제 교집합을 구할 차례이다. 교집합은 두 집합 모두에게 존재해야 한다. 따라서 필자는 a의 key값을 b에 대입해 볼 것이다. 만약 b에 값이 존재한다면 a와 b에 있는 값 중 작은 값이 들어가도록 했다. 아래에 보면 union은 합집합인데 a를 일단 넣어두려고 반복문안에 넣었다.
1 | Iterator<String> b_keys = b.keySet().iterator(); |
이제 합집합을 구하는데 아까 위에서 a에 대한 값은 미리 넣어주었으므로 이제 b에 대해서 삽입하면 된다. 합집합에 공통원소가 있을 경우 더 큰 값을 쓰기 때문에 max를 이용하여 값을 넣는다.
1 | Iterator<String> inter_keys = inter.keySet().iterator(); |
이제 자카드 유사도를 구할 차례이다. inter_size와 union_size를 선언하고 value들을 전부 합한 값을 담는다. 이때 union_size를 0으로 초기화하지 않은 이유는 0으로 나눴을 때 예외가 발생하기 때문에 컴파일을 애초에 해주지 않기 떄문이다. 그래서 1로 선언하고 나중에 다시 1을 감소시킨다. 나눈 두 값으로 자카드 유사도를 구했다.
최종 시간복잡도는 공비가 \(1\over2\)인 등비수열의 합이므로, 2진법을 계산하는 과정이 있기 때문에 \(O(n*{1\over2}^n)\)이다.
테스트
