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

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

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

 

문자열을 비교하고, 교집합/합집합 개념을 이용하는 문제! 예외 케이스들을 유의해서 작성해줘야한다. 

합집합은 보통 A + B - (A와 B의 교집합)으로 구하게 되는데, A와 B가 아예 겹치지 않는 경우 등을 사전에 고려해야 한다. 

 

문제의 예시를 보고 이해해보자. 

 

FRANCE와 FRENCH의 자카드 유사도를 구해주면 된다. (자카드 유사도 = 교집합 / 합집합 수)

 

FRANCE	FRENCH
["FR"."RA","AN","NC","CE"]	["FR","RE","EN","NC","CH"]

2개씩 끊어주면 위와 같이 나오게 된다. 

여기서 교집합과 합집합을 찾아주면 된다.

 

FRANCE	FRENCH	교집합	합집합
["FR"."RA","AN","NC","CE"]	["FR","RE","EN","NC","CH"]	["FR","NC"]	["FR"."RA","RE","EN","AN","NC","CE","CH"]

즉 2/8로 0.25가 도출되게 된다. 

문제에서는 최종 결과값에 65536을 곱한 값을 리턴하라고 했으니 곱해주기만 하면 된다. 

 

이에 우선 교집합 / 합집합을 구하는 함수를 먼저 보자.

맨 처음에는 Set을 이용해서 기본 함수를 쓰면 되겠다! 라고 생각했는데 아래와 같은 예외 케이스가 있어서 쓰지 못했다. 

 

["aa","aa"] ["aa","aa","aa"] 

 

이렇게 같은 원소로 이루어져있는 배열을 Set으로 변환하게 되면 다 동일하게 보기 때문에 값이 달라지게 된다. 그렇기에 기존 배열에 기반해서 구하는 방식을 고안해야한다. 

 

func interUnion(_ str1: [String], _ str2: [String]) -> [Int] {
    var dict1 = [String:Int]()
    var dict2 = [String:Int]()
    var minCnt = 0
    var maxCnt = 0
    
    for s in str1 {
        dict1[s, default: 0] += 1
    }
    
    for s in str2 {
        dict2[s, default: 0] += 1
    }
    
    // 1을 기준으로 2에도 있으면 교집합,합집합 추가, 2에 없으면 합집합 추가
    for (k,v) in dict1 {
        if dict2[k] != nil {
            minCnt += min(v, dict2[k]!)
            maxCnt += max(v, dict2[k]!)
        } else {
            maxCnt += v
        }
    }
    // 2에만 있는 것
    for (k,v) in dict2 {
        if dict1[k] == nil {
            maxCnt += v
        }
    }
    
    return [minCnt,maxCnt]
}

dictionary 객체를 통해 교집합, 합집합 수를 카운트해준다. 

먼저 dictionary keys를 채워주고 2를 기준으로 1을 살펴보고, 1을 기준으로 2를 살펴봐준다. 

교집합은 최소로 합집합은 최대의 개념으로 접근하여 구해준다. 

 

같은 원소가 2개 1개 있다고 해도 교집합은 1개이기에 min으로 접근해주고 합집합은 계속 더해나가기 위해 max로 접근하여 카운팅 해준다. 

 

1. 1번을 기준으로 2번의 딕셔너리를 보며 교집합,합집합을 채워준다.
2. 2번에서 못건드린걸 돌면서 합집합에만 추가한다. 이미 교집합은 봐뒀기 때문

 

그리고 문자열을 2개 단위로 쪼개주는 함수도 필요하다. 

func prepare(_ str: String) -> [String] {
    let newstr = str.map {String($0.lowercased())}
    var ans = [String]()
    
    for i in 1..<newstr.count {
        if Character(newstr[i-1]).isLetter && Character(newstr[i]).isLetter {
            ans.append(newstr[i-1] + newstr[i])    
        }        
    }
    return ans
}

문자인 경우에만 걸러서 2개씩 이어붙어줬다. 

 

이제 최종 코드를 봐보자!

 

import Foundation 

func solution(_ str1:String, _ str2:String) -> Int {
    let newstr1 = prepare(str1)
    let newstr2 = prepare(str2)
    let interCnt = interUnion(newstr1,newstr2)[0]
    let unionCnt = interUnion(newstr1,newstr2)[1]
    
    if unionCnt == 0 && interCnt == 0 {
        return 65536
    } 
    
    return Int(floor((Double(interCnt) / Double(unionCnt)) * 65536))
}

이렇게 보니까 별거 없다!

 

[프로세스]

 

1. 2개 단위 문자열로 쪼개준다 (prepare)

2. 교집합과 합집합을 구해준다. (interUnion)

3. 교집합, 합집합 둘 중에 하나라도 0인 경우 1을 반환하고 65536을 곱해줘야하기에, 65536을 리턴한다. 

4. 0이 아닌 경우 자카드 유사도를 구하여 65546을 곱하고 내림해준다!

 

---

교집합, 합집합을 구하는 부분에서 조금 헤맸던 것 같다. 예외 케이스를 항상 염두에 두어야 할 것 같고, 딕셔너리 이외에도 다른 자료구조로 구할 수 있는지도 봐야할 것 같다.