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

 

문제 해석

---

 

Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 뉴스 검색 문제점 개선을 업무를 맡았다고 합니다. 사용자에게 더욱 다양하고 편리한 검색 결과를 제공하기 위해 자카드 유사도를 활용하여 유사한 기사들을 묶어 제공해보기로 했습니다.

자카드 유사도는 집합 간의 유사도를 검사하는 방법으로 두 집합간의 교집합의 크기를 두 집합간의 합집합의 크기로 나눈 값을 의미합니다.

이 자카드 유사도를 원소의 중복을 허용하는 다중집합에서 확장시키게 되면 교집합은 두 집합 모두 포함하는 원소를 최소 개수만큼을 포함하고 합집합은 두 집합에서 포함하는 원소를 최대 개수만큼을 포함합니다.

예를 들어 두 다중집합 A = { "AA", "AA", "AA", "BB"} , B = {"AA", "AA"} 가 있다고 해봅시다. 

그렇게 되면 두 다중집합의 교집합은 두 집합에서 같이 등장하는 "AA"의 최소 포함 개수인 2만큼 가지게 되고 합집합은 "AA"의 최대 등장 개수인 3만큼 가지고 "BB"의 최대 등장 회수인 1 만큼 가지게 됩니다.

교집합 = { "AA", "AA" }

합집합 = { "AA", "AA" ,"AA", "BB" }

두 문자열을 입력 받아 자카드 유사도를 구하게 되는데 문자열을 2문자씩 끊어서 다중집합을 형성합니다.

대소문자를 구별하지 않고 알파벳만 취급합니다. 두 집합 모두 공집합일 때는 자카드 유사도를 1로 정의합니다.

문제 해결 & 코드

---

import Foundation

func solution(_ str1:String, _ str2:String) -> Int {
    // 대소문자를 구별하지 않기 위해 대문자로 통일합니다.
    // .map{$0}을 사용하여 추후 두 문자씩 묶어주기 위한 작업이 편하도록 배열로 변환합니다.
    
    let capitalStr1 = str1.uppercased().map{$0}
    let capitalStr2 = str2.uppercased().map{$0}
    
    // 교집합,합집합 배열
    
    var intersection = [String]()
    var union = [String]()
    
    // 튜플의 첫 번째 값은 해당 Key인 문자를 A에서 포함하는 개수이고
    // 두 번째 값은 B에서 포함하는 개수를 의미합니다.
    
    var countDict: Dictionary<String, (Int, Int)> = [:]
    
    // 대문자 알파벳만 필터링 하기 위한 함수
    
    func isAlphabet(_ character: Character) -> Bool {
        return character >= "A" && character <= "Z"
    }
    
    // 입력받은 첫 번째 문자열을 통해 다중 집합 A를 딕셔너리에 저장합니다.
    // 따라서 튜플의 첫 번째 값에 포함 개수를 저장합니다.
    
    for idx in 0..<capitalStr1.count - 1 {
        
        if isAlphabet(capitalStr1[idx]) == false || isAlphabet(capitalStr1[idx+1]) == false {
            continue
        }
        
        let temp = "\(capitalStr1[idx])\(capitalStr1[idx+1])"
        
        // 존재하는 경우 포함 개수 += 1, 없는 경우 (1, 0)
        
        if countDict[temp] != nil {
            countDict[temp]!.0 += 1
        } else {
            countDict[temp] = (1, 0)
        }
    }
    
    // 입력받은 두 번째 문자열을 통해 다중 집합 B를 딕셔너리에 저장합니다.
    // 따라서 튜플의 두 번째 값에 포함 개수를 저장합니다.
    
    for idx in 0..<capitalStr2.count - 1 {
        if isAlphabet(capitalStr2[idx]) == false || isAlphabet(capitalStr2[idx+1]) == false {
            continue
        }
        
        let temp = "\(capitalStr2[idx])\(capitalStr2[idx+1])"
        
        if countDict[temp] != nil {
            countDict[temp]!.1 += 1
        } else {
            countDict[temp] = (0, 1)
        }
    }
    
    // 딕셔너리가 비어있는 경우 A, B 모두 공집합을 의미하므로 
    // 자카드 유사도를 1로 정의하고 리턴합니다.
    
    if countDict.isEmpty {
        return 1 * 65536
    }
    
    // 딕셔너리를 탐색하며 포함개수를 비교하여 교집합과 합집합에 해당 문자를 넣어줍니다.
    
    for (key, value) in countDict {
        let maxVal = max(value.0, value.1)
        let minVal = min(value.0, value.1)
        for _ in 0..<maxVal {
            union.append(key)
        }
        for _ in 0..<minVal {
            intersection.append(key)
        }
    }
   
    return Int(Double(intersection.count)/Double(union.count) * 65536)
}