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

문제

https://programmers.co.kr/learn/courses/30/lessons/17677

자카드 유사도 -> 집합간 유사도를 검사하는 여러가지 방법 중 하나

-> 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값

두 집합 a,b의 자카드 유사도 = J(a, b)

문제는 간단. 두 문자열을 입력 받고, 각각의 문자열을 두칸씩 나눠서(두칸 모두 알파벳일 경우만) 배열 2개를 만들어서

두 배열의 (교집합 / 합집합) * 65536 의 값에서 소수점을 버린 값을 return 하는 문제.

예로 문자열 FRANCE와 FRENCH가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.

• 대소문자 무시.

접근방법

교집합만 구하면 끝나는 문제. 단 각 array가 중복값을 허용하기 때문에 신경써서 구해줘야 한다.

합집합 = arr1 + arr2 - 교집합

굳이 배열을 구하려 하지 말고 수만 생각해서 구하자. 필요한건 집합 갯수..

코드

	import Foundation
	func solution(_ str1:String, _ str2:String) -> Int {
	var v1: [String] = []
	var v2: [String] = []
	for i in 0 ..< str1.count-1 {
	let sttIdx = str1.index(str1.startIndex, offsetBy: i)
	let endIdx = str1.index(str1.startIndex, offsetBy: i+1)
	if str1[sttIdx].isLetter && str1[endIdx].isLetter {
	v1.append(String(str1[sttIdx...endIdx]).lowercased())
	}
	}
	for i in 0 ..< str2.count-1 {
	let sttIdx = str2.index(str2.startIndex, offsetBy: i)
	let endIdx = str2.index(str2.startIndex, offsetBy: i+1)
	if str2[sttIdx].isLetter && str2[endIdx].isLetter {
	v2.append(String(str2[sttIdx...endIdx]).lowercased())
	}
	}
	if v1.isEmpty && v2.isEmpty { return 65536 }
	let a = intersect(v1, other: v2)
	let b = sumArrayCount(v1, other: v2)
	let rst = Int(floor((Double(a) / Double(b)) * 65536))
	return rst
	}
	func sumArrayCount(_ base: [String], other: [String]) -> Int {
	let sameArray = intersect(base, other: other)
	return base.count + other.count - sameArray
	}
	func intersect(_ base: [String], other: [String]) -> Int {
	var result = 0
	var dic: [String:Int] = [:]
	other.forEach {
	if dic[$0] != nil {
	dic[$0]! += 1
	} else { dic[$0] = 1}
	}
	base.forEach {
	if let v = dic[$0], v >= 1 {
	result += 1
	dic[$0]! -= 1
	}
	}
	return result
	}

view raw 클러스터링.swift hosted with ❤ by GitHub