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

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/17677?language=swift 

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

문제 요약

 유사한 기사를 묶는 기준을 정하기 위해 "자카드 유사도"라는 방법을 찾아냈다.

 

 자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중 하나로,

 두 집합 A,B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값을 정의된다.

 

 집합 A,B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 J(A,B) = 1로 정의한다.

 문자열 사이의 유사도를 계산할 때는, 두 글자씩 끊어서 다중집합을 만들도록 한다.

 

 // 입력 형식

• str1, str2의 두 문자열이 들어온다.
•  문자열을 두 글자씩 끊어서 다중 집합의 원소로 만든다.
• 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수문자가 들어있는 경우 그 글자 쌍을 버린다.
  ( ex. ab+가 들어오면 ab만 다중집합의 원소로 삼고, b+는 버린다. )
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. 같은 원소로 취급한다.

 

 // 출력 형식

•  입력을 들어온 두 문자열의 자카드 유사도를 출력한다.
•  유사도 값은 0-1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

 

풀이 코드

• 코드 안에 주석으로 설명을 해두었습니다. 참고해주세요!

func cutString(_ str: String) -> [String] {
  var rst: [String] = []
  
  for i in 0..<str.count - 1 {
    let startIndex = str.index(str.startIndex, offsetBy: i)
    let endIndex = str.index(str.startIndex, offsetBy: i + 1)

    if str[startIndex].isLetter && str[endIndex].isLetter {
      rst.append(String(str[startIndex...endIndex]).lowercased())
    }
  }
  return rst
}

// 합집합 개수 구하기
func union(_ base: [String], target: [String]) -> Int {
  return base.count + target.count - intersect(base, target: target)
}

// 교집합 개수 구하기
func intersect(_ base: [String], target: [String]) -> Int {
  var result: Int = 0
  var dict: [String: Int] = [:]
  
  target.forEach { elem in
    if dict[elem] != nil {
      dict[elem]! += 1
    } else {
      dict[elem] = 1
    }
  }
  
  base.forEach { elem in
    if let e = dict[elem], e >= 1 {
      result += 1
      dict[elem]! -= 1
      print(1)
    }
  }
  return result
}

func solution(_ str1:String, _ str2:String) -> Int {
  // 다중집합 구하기
  let s1 = cutString(str1)
  let s2 = cutString(str2)
  
  // 둘 다 공집합인 경우, 유사도는 1
  if s1.isEmpty && s2.isEmpty { return 65536 }
  
  // 두 다중집합을 비교해서 유사도 계산하기 : 교집합 개수 / 합집합 개수
  let a = Double(intersect(s1, target: s2)) // 교집합 개수 구하기 (b)
  let b = Double(union(s1, target: s2)) // 합집합 개수 구하기 (a)
  a/b
  // 유사도 * 65536
  return Int(floor((a / b) * 65536))
}

 

 

틀린부분이 있거나, 더 좋은 방법이 있다면 댓글로 남겨주세요! 
🌈댓글은 언제나 환영입니다🙏🏻