[알고리즘]프로그래머스 17677번 - [1차] 뉴스 클러스터링

프로그래머스 17677번 - [1차] 뉴스 클러스터링

프로그래머스 17677번 - https://programmers.co.kr/learn/courses/30/lessons/17677

 

요구사항

1. 두 문자열의 자카드 유사도 값에 65536을 곱한 후 소수점 아래를 버린 정수부를 반환하라.

 

요구사항 분석 및  풀이과정

자카드 유사도를 구하기 위하여 다중집합을 구성하여야 한다.

다중집합은 주어진 문자열을 두 글자씩 끊어 다중집합의 원소로 한다.

 

단, 영문자로 된 글자 쌍만 유효하며, 기타 공백이나 숫자, 특수 문자가 들어있는 경우에는 그 글자 쌍을 버리며 대소문자는 구별하지 않는다.

 

자카드 유사도는 두 다중집합 A, B에 대하여 (교집합의 원소의 수 / 합집합의 원소의 수)로 정의되며, 만약 두 다중집합 A, B가 모두 공집합일 경우 자카드 유사도는 1로 정의한다.

 

자카드 유사도

자카드 유사도

 

다중집합 A, B에 대하여 합집합(A or B)은 다음과 같이 정의합니다. 

 

n(A or B) = n(A-B) + n(B-A) + n(공통 원소가 최대한으로 포함된 두 다중집합의 교집합)

n(A and B) = n(공통 원소가 최소한으로 포함된 두 다중집합의 교집합)

 

 

이 문제에서는 다중집합을 자카드 집합(Jaccard Set)이라고 하겠습니다. 저희는 두 자카드 집합에 대하여 자카드 유사도를 구하는 것이 목적입니다.

 

1. 주어진 두 문자열을 주어진 조건에 맞게 두 글자씩 끊어 자카드 집합의 원소로 하여 각각 자카드 집합으로 변환합니다.

2. 두 자카드 집합에 대하여 다음을 구합니다.

 

n(A-B)

n(B-A)

n(공통 원소가 최대한으로 포함된 두 다중집합의 교집합)

n(공통 원소가 최소한으로 포함된 두 다중집합의 교집합)

 

3. 자카드 유사도 공식에 의하여 계산을 한 후, 65536을 곱한 후 소수점 아래를 Math.floor 메서드를 이용하여 버린 후, int 형으로 변환하여 정수부를 반환합니다.

 

소스코드 작성

class Solution {

	private static class JaccardSet {

		private final Map<String, Integer> set;
		private static final int FACTOR = 65536;

		public JaccardSet(String str) {
			this.set = generateSet(str);
		}

		private Map<String, Integer> generateSet(String str) {
			Map<String, Integer> tokens = new HashMap<>();

			for (int idx = 0; idx < (str.length() - 1); idx++) {
				if (!Character.isLetter(str.charAt(idx)) || !Character.isLetter(str.charAt(idx + 1))) {
					continue;
				}

				String key = str.substring(idx, idx + 2).toLowerCase();
				tokens.put(key, tokens.getOrDefault(key, 0) + 1);
			}

			return tokens;
		}

		private int numOfDifference(JaccardSet other) {
			int result = 0;

			for (Map.Entry<String, Integer> entry : set.entrySet()) {
				if (!other.set.containsKey(entry.getKey())) {
					result += entry.getValue();
				}
			}

			return result;
		}

		private int numOfIntersection(JaccardSet other, BiFunction<Integer, Integer, Integer> cmp) {
			int result = 0;

			for (Map.Entry<String, Integer> entry : set.entrySet()) {
				if (other.set.containsKey(entry.getKey())) {
					result += cmp.apply(entry.getValue(), other.set.get(entry.getKey()));
				}
			}

			return result;
		}

		private int calculateSimilarity(int common, int total) {
			if (common == 0 && total == 0) {
				return FACTOR;
			}

			double similarity = (double)common / total;
			return (int)Math.floor(similarity * FACTOR);
		}

		public int similarity(JaccardSet other) {
			int minOfCommon = this.numOfIntersection(other, Math::min);
			int maxOfCommon = this.numOfIntersection(other, Math::max);
			int total = this.numOfDifference(other) + other.numOfDifference(this) + maxOfCommon;

			return calculateSimilarity(minOfCommon, total);
		}
	}

	public int solution(String str1, String str2) {
		return new JaccardSet(str1).similarity(new JaccardSet(str2));
	}
}

 

결과

 

소스코드 깃허브 주소

링크

 

마무리

단순히 빠른 시간내에 푸는 코딩 테스트 문제라고 할지라도 최대한 객체적인 사고를 하면서 짜려고 하고 있습니다. 문제를 푸는 것만에 초점을 맞출 경우 코드의 수를 대폭 줄일 수 있습니다. 속도 또한 ms 단위지만 2~10배까이 빠르게 할 수 있습니다.

 

이 말을 적는 이유는, 간혹 제 풀이에 쓸데 없이 클래스를 만들고 사용하는 방식의 문제풀이 방법이 의아해하실 분들 위하여 적습니다.