programmers. 뉴스 클러스터링(소요시간 : 80분)
풀면 그렇게 어렵지 않았는데 시간이 조금 오래걸린게 아쉽습니다. 문제 이해하고 분석하여 코드를 짜기전까지 20 ~ 30분 정도 걸린 것 같습니다. 아마도 문제에 '자카드 유사도'와 같은 겁먹게 하는 용어가 있어서 그런 것 같기도 합니다. 문제는 다음 3단계로 나누어 풀었습니다.
문제열을 쪼개 집합 2개를 만듭니다.
- 이때 각 집합에 대한 자료형은
Map<String, Integer>
로 합니다. - 처음에 이를
List<String>
으로 하려했는데 중복 계산이 복잡할 것 같아Map
으로 바꾸었습니다. 이를 바꾼게 탁월한 선택이었습니다.
- 이때 각 집합에 대한 자료형은
두 집합의 합집합, 교집합을 구합니다.
중복처리에 유념합니다.
- map1 의 반복문을 돌려 map2에 있는지 찾고 있으면 계산 후 map2의 키를 지워줍니다.
- map1 반복문이 끝나면 map2에 남아있는 값들을 합집합에 모두 더해줍니다. 그 이유는 map2에는 교집합 원소들이 남아있지 않기 때문입니다.
합집합, 교집합은 따로 Collection에 담을 필요없이 그 수를 바로 더해주면 되기 때문에
int
를 사용합니다.
합집합, 교집합 수에 맞춰 출력값을 구합니다.
- 소수점 계산에 주의합니다.
- 공집합일 경우를 고려합니다.
시간이 좀 소요된 부분이 처음에 집합 2개를 만드는 부분입니다. 여기서 영문자만 저장되도록 제한해야했고, 대소문자 구별이 없도록 해야하는 등의 세세한 작업이 필요했기 때문입니다. 그런데 이 부분도 TDD기반으로 만들고 있는데 그러다보니 좀 더 시간이 소요되었던 것 같습니다. 이제는 TDD없이 코드 짜는 것이 불안하게 되어 계속 그런 식으로 코드를 짜게되는데 알고리즘 풀 때는 중요 알고리즘 이외엔 TDD없이 짜보는 연습을 좀 더 연습해야할 것 같습니다.
class Solution {
public int solution(String str1, String str2) {
Map<String, Integer> map1 = init(str1);
Map<String, Integer> map2 = init(str2);
double intersection = 0;
double union = 0;
for (String s : map1.keySet()) {
if(map2.containsKey(s)) {
intersection += Math.min(map1.get(s), map2.get(s));
union += Math.max(map1.get(s), map2.get(s));
map2.remove(s);
continue;
}
union += map1.get(s);
}
for (String s : map2.keySet()) {
union += map2.get(s);
}
double divied;
if(union == 0.0) divied = 1;
else divied = intersection / union;
return (int)(divied * 65536);
}
public Map<String, Integer> init(String str) {
Map<String, Integer> map = new HashMap<>();
char[] charStr = str.toCharArray();
return mapInit(map, charStr);
}
private Map<String, Integer> mapInit(Map<String, Integer> map, char[] charStr) {
for (int i = 0; i < charStr.length - 1; i++) {
if(isValid(charStr[i]) && isValid(charStr[i + 1])){
StringBuilder sb = new StringBuilder();
sb.append(toUpperCase(charStr[i]));
sb.append(toUpperCase(charStr[i + 1]));
String text = sb.toString();
int num = map.getOrDefault(text, 0);
map.put(text, num + 1);
}
}
return map;
}
char toUpperCase(char c) {
if(c >= 'a' && c <= 'z') return (char) (c - 32);
return c;
}
boolean isValid(char c) {
return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
}
}
'Algorithm > problem solving' 카테고리의 다른 글
Today's Algorithm(2019-02-22) (0) | 2019.02.22 |
---|---|
Today's Algorithm(2019-02-14) (0) | 2019.02.14 |
Today's Algorithm(2019-02-07) (0) | 2019.02.07 |
Today's Algorithm(2019-02-06) (0) | 2019.02.06 |
Today's Algorithm(2019-02-05) (0) | 2019.02.05 |