개발일지/Algorithm
프로그래머스 - 뉴스 클러스터링 [자바]
E-room
2023. 11. 28. 15:59
728x90
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
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. 전체 코드
728x90