[프로그래머스] 2018 카카오 블라인드 코딩테스트 - 뉴스 클러스터링 (Swift 풀이)

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

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

 

 

문자열을 두 글자씩 자르기

문자열 쪼개는 데에 시간이 한참 걸렸다...!!!!

 

미래의 내가 까먹지 않도록 정리하는 내용

• 문자열 인덱스로 subscript를 사용하면 -> String이 아니라 Substring 타입이 반환됨!!!
• Range<Int>는 (n...m) 형태 말고, (n..<m) 형태로 써야 동작하더라..

str로부터 인덱스 i 부터 2글자를 가져오려면 String.Index를 이용한다.

let firstIdx = str.index(str.startIndex, offsetBy: i)
let lastIdx = str.index(str.startIndex, offsetBy: i+2)
let substring = String(str[firstIdx..<lastIdx])

 

extension을 활용하여 String.Index를 구해서 접근하는 대신, Int 값으로도 접근할 수 있게 만들어보자.

extension String {
    subscript(_ range: Range<Int>) -> String {
        let fromIndex = self.index(self.startIndex, offsetBy: range.startIndex)
        let toIndex = self.index(self.startIndex,offsetBy: range.endIndex)
        return String(self[fromIndex..<toIndex])
    }
}

let substring = str[i..<i+2]

 

이제 str1과 str2의 전체 substring을 구해보자.

반복문을 돌려 i를 0부터 str.count-2까지 돌린다.

for i in 0..<str1.count-1 {
    let substring1 = str1[i..<i+2]
    ...
}
    
for i in 0..<str2.count-1 {
    let substring2 = str2[i..<i+2]
    ...
}

 

이렇게 쪼갠 문자열은 대소문자 구분을 하지 않고, 영문 알파벳으로만 이루어져야 한다.

대소문자 구분을 없애기 위하여 .lowercased()를 사용해 모두 소문자로 만들어 준다.

그리고, 정규식을 활용하여 쪼갠 문자열이 알파벳으로만 이루어져 있는지 확인 한다.

func isAlphabet(_ str: String) -> Bool {
    let pattern = "^[a-z]*$"
    return str.range(of: pattern, options: .regularExpression) != nil
}

let substring1 = str1[i..<i+2].lowercased()
if isAlphabet(substring1) {
    ....
}

 

 

중복 집합? 어떻게 표현하지??

중복집합의 교집합과 합집합의 개수를 구해야 하는데..

str1과 str2를 2글자씩 쪼갠 부분문자열들을 어디에 넣어야 할까!

Array에 넣으면 두 중복 집합에서 같고 다른 것을 찾기 어려울 것이다.

Set에 넣으면 같은 값을 넣었을 때 중복은 제외되버린다.

 

그래서 Dictionary에 key에 부분문자열을 넣고, value에 해당 부분 문자열의 개수를 넣어주었다. (st1, str2 각각)

var dict1: [String:Int] = [:]
var dict2: [String:Int] = [:]

for i in 0..<str1.count-1 {
    let substring1 = str1[i..<i+2].lowercased()
    if isAlphabet(substring1) {
        if dict1[substring1] != nil {
            dict1[substring1]! += 1
        } else {
            dict1[substring1] = 1
        }
    }
}    
for i in 0..<str2.count-1 {
    let substring2 = str2[i..<i+2].lowercased()
    if isAlphabet(substring2) {
        if dict2[substring2] != nil {
            dict2[substring2]! += 1
        } else {
            dict2[substring2] = 1
        }
    }
}

 

 

교집합과 합집합 개수 구하기

dict1 또는 dict2에 있는 모든 key들에 대하여 개수를 세어보아야 하므로,

dict1.keys, dict2.keys를 Set으로 변환하고, union (합집합) 연산을 수행해준다.

let keySet = Set(dict1.keys).union(Set(dict2.keys))

 

특정 key에 대하여 교집합 개수는 min(dict1[key], dict2[key) 이고, 합집합 개수는 max(dict1[key], dict2[key]) 이다.

이 과정을 모든 keySet에 대하여 반복하며 교집합과 합집합 개수를 구한다.

var intersectionCount = 0
var unionCount = 0
for key in keySet {
    if let value1 = dict1[key], let value2 = dict2[key] {
        let min = value1 < value2 ? value1 : value2
        let max = value1 > value2 ? value1 : value2
        intersectionCount += min
        unionCount += max
    } else if let value1 = dict1[key] {
        unionCount += value1
    } else if let value2 = dict2[key] {
        unionCount += value2
    }
}

 

 

자카드 유사도 구하기

자카드 유사도는 (교집합 개수 / 합집합 개수) 로 구할 수 있다.

단, 이 문제에서는 자카드 유사도에 65536을 곱한 값을 반환하도록 조건이 설정되어 있다.

 

만약, 나누는 수가 0이면 계산할 수 없다. 이런 경우에는 자카드 유사도를 1로 정하였다.

나누는 수 (합집합 개수)가 0인 경우는, 두 중복집합 개수가 모두 0인 경우를 말한다!

이 경우는 합집합, 교집합을 구하기 전에 처리해주는 것이 효율적이다.

if dict1.isEmpty && dict2.isEmpty {
    return 65536
}

 

일반적인 경우에 대한 반환 조건은 다음과 같다.

let result = Float(intersectionCount) / Float(unionCount) * 65536
return Int(result)

 

 

전체 코드

import Foundation

extension String {
    subscript(_ range: Range<Int>) -> String {
        let fromIndex = self.index(self.startIndex, offsetBy: range.startIndex)
        let toIndex = self.index(self.startIndex,offsetBy: range.endIndex)
        return String(self[fromIndex..<toIndex])
    }
}

func isAlphabet(_ str: String) -> Bool {
    let pattern = "^[a-z]*$"
    return str.range(of: pattern, options: .regularExpression) != nil
}

func solution(_ str1:String, _ str2:String) -> Int {

    // 2글자 부분문자열로 이루어진 중복 집합을 구한다.
    var dict1: [String:Int] = [:]
    var dict2: [String:Int] = [:]
    
    for i in 0..<str1.count-1 {
        let substring1 = str1[i..<i+2].lowercased()
        if isAlphabet(substring1) {
            if dict1[substring1] != nil {
                dict1[substring1]! += 1
            } else {
                dict1[substring1] = 1
            }
        }
    }
    
    for i in 0..<str2.count-1 {
        let substring2 = str2[i..<i+2].lowercased()
        if isAlphabet(substring2) {
            if dict2[substring2] != nil {
                dict2[substring2]! += 1
            } else {
                dict2[substring2] = 1
            }
        }
    }
    
    // 합집합이 0인 경우(두 집합이 모두 비어있을 경우)는 나눌 수 없다.
    if dict1.isEmpty && dict2.isEmpty {
        return 65536
    }
    
    // 자카드 유사도 구하기 = 교집합개수 / 합집합개수
    let keySet = Set(dict1.keys).union(Set(dict2.keys))
    var intersectionCount = 0
    var unionCount = 0
    for key in keySet {
        if let value1 = dict1[key], let value2 = dict2[key] {
            let min = value1 < value2 ? value1 : value2
            let max = value1 > value2 ? value1 : value2
            intersectionCount += min
            unionCount += max
        } else if let value1 = dict1[key] {
            unionCount += value1
        } else if let value2 = dict2[key] {
            unionCount += value2
        }
    }
    
    // 반환값은 자카드유사도 * 65536 그리고 소수점 버리기
    let result = Float(intersectionCount) / Float(unionCount) * 65536
    return Int(result)
}