2018 KAKAO BLIND RECRUITMENT [1차] 뉴스 클러스터링 Swift

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

Foma's 풀이

 

문제풀이

 

이번 문제는 자카드 유사도를 통해 두 문장을 비교해 그에 따른 유사도 값을 구하는 것인데요,

 

그렇다면 자카드 유사도가 무엇일까요?

 

자카드 유사도란 문서의 유사도를 구하기 위한 기법 중 하나인데요.

 

우선 예시로 설명 드리면 두 문장 A : [안녕 나는 포마야, iOS 공부를 하고 치킨을 좋아해 사는 곳은 서울에 있는 홍대야 ]  와 B : [안녕, 나는 마포야. iOS 개발을 하고 피자를 좋아해. 사는 곳은 서울에 있는 신촌이야.] 가 있다고 가정하겠습니다.

 

그럼 두 문장에서 겹치는 부분 먼저 살펴보면 [안녕, iOS, 좋아해, 하고, 사는, 곳은, 서울에, 있는] 이 될 것입니다. -> 교집합

 

그리고 두 문장을 합치면 [안녕 나는 포마야, iOS 공부를 하고 치킨을 좋아해 사는 곳은 서울에 있는 홍대야 , 마포야, 개발을 , 피자를 , 신촌이야] 가 될 것입니다. -> 합집합

 

여기서 합집합의 갯수(17)를 교집합의 갯수(8)로 나누게 되면 0.47... 이 되는데 이것이 바로 자카드 유사도 값이 됩니다.

 

코드풀이

 

문제에서 대소문자 구별은 하지 않는다고 했으므로 str1과 str2를 일괄적으로 소문자로 만들어줍니다. 또 문자열을 다루기 쉽게 각 캐릭터를 배열화 시켜주기 위해 map을 사용해줍니다. 

 

->  let lowerStr1 = str1.lowercased().map{$0},    let lowerStr2 = str2.lowercased().map{$0}

 

str1과 str2를 두문자로 끊은 글자들을 담을 배열을 만들어줍니다.

 

- >     var set1 = [String]() ,var set2 = [String]()

 

두 문장이 겹치는 부분 교집합을 담을 배열과 두 문장을 합친 합집합을 담을 배열을 만들어 줍니다.

 

- >   var intersection = [String]() , var union = [String]()

 

먼저 소문자로 만들어준 lowerStr1을 for문을 사용하여 끝까지 순회합니다. - >   for i in 0..<lowerStr1.count-1 {...}

 

조건에서 영문이 아닌 글자가 포함되면 버린다고 하였으므로 2글자 모두 영문인지 확인하고 맞다면 set1에 담아줍니다. -> if isAlphabet(lowerStr1[i], lowerStr1[i+1]) { set1.append("\(lowerStr1[i])\(lowerStr1[i+1])") }

 

위에 isAlphabet 함수를 사용하였는데 이것은 문자가 맞는지 아닌지 확인해줍니다.

 

-> func isAlphabet(_ char1 :Character,_ char2:Character) -> Bool {

   return char1 >= "a" && char1 <= "z" && char2 >= "a" && char1  <= "z" }

 

lowerStr2도 마찬가지로 for문을 사용하여 순회하고 isAlphabet을 사용하여 확인하고 set2에 넣어줍니다.

 

- >  for i in 0..<lowerStr2.count-1{

        if isAlphabet(lowerStr2[i], lowerStr2[i+1]) {

            let twoLetters = "\(lowerStr2[i])\(lowerStr2[i+1])"

            set2.append(twoLetters)

 

그리곤 바로 set1에 해당 두글자가 포함되어 있다면 겹치는 부분이므로 intersection에 넣어주고 set1,set2에서 각 각 삭제해줍니다.

 

>  if set1.contains(twoLetters) {

                intersection.append(twoLetters)

                set1.remove(at: set1.firstIndex(of: twoLetters)!)

                set2.remove(at: set2.firstIndex(of: twoLetters)!)

            }

 

for문이 끝난 뒤 set1과 set2를 합치고 겹치는 부분인 교집합까지 합쳐줘 합집합을 만들어줍니다.

 

- > union = set1 + set2 + intersection

 

마지막으로 교집합고 합집합이 모두 비었을 때(공집합)는 문제에서 정의되지 않으므로 1으로 간주한다고 되어있습니다. 고로 모두 공집합일 땐 1에 65536을 곱합 값을 반환하고 아니라면 합집합에서 교집합을 나눈 뒤 65536을 곱합 정수값을 반환해줍니다. - > 

 

 return intersection.isEmpty && union.isEmpty ? 65536 :Int(Double(intersection.count)/Double(union.count)*65536)

           

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

func solution(_ str1:String, _ str2:String) -> Int {     let lowerStr1 = str1.lowercased().map{$0}     let lowerStr2 = str2.lowercased().map{$0}     var set1 = [String]()     var set2 = [String]()     var intersection = [String]()     var union = [String]()          for i in 0..<lowerStr1.count-1 {         if isAlphabet(lowerStr1[i], lowerStr1[i+1]) {             set1.append("\(lowerStr1[i])\(lowerStr1[i+1])")         }     }          for i in 0..<lowerStr2.count-1{         if isAlphabet(lowerStr2[i], lowerStr2[i+1]) {             let twoLetters = "\(lowerStr2[i])\(lowerStr2[i+1])"             set2.append(twoLetters)             if set1.contains(twoLetters) {                 intersection.append(twoLetters)                 set1.remove(at: set1.firstIndex(of: twoLetters)!)                 set2.remove(at: set2.firstIndex(of: twoLetters)!)             }         }     }          union = set1 + set2 + intersection          return intersection.isEmpty && union.isEmpty ? 65536 :Int(Double(intersection.count)/Double(union.count)*65536) }   func isAlphabet(_ char1 :Character,_ char2:Character) -> Bool {    return char1 >= "a" && char1 <= "z" && char2 >= "a" && char1  <= "z" } Colored by Color Scripter