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

문제: programmers.co.kr/learn/courses/30/lessons/17677

 

<조건>

• 두 문자열 str1, str2가 입력으로 주어진다. 
• J(A, B) = $\frac{A∩B}{A∪B}$
• 대문자와 소문자는 구분하지 않는다.
• 각 문자열을 두 글자씩 쪼갠다.
  
  • 이때, 영문자로만 이루어진 글자 쌍만 유효하다.
  • ex) aa1+aa2 
    • 단순히 두 글자로 쪼개면 {aa, a1, a+, +a, aa, a2}가 되지만, 유효한 집합은 다음과 같다.
    • => {aa, aa}
• [ J({str1}, {str2})*65536 ]을 구하라!

 

문제 풀이:

 

1. 먼저 각 문자열을 소문자로 통일하였다. 
   • 어떤 대문자 C에 대해 char(C-'A'+'a') 연산을 하면, 소문자로 변환할 수 있다. 
   • 변환한 문자가 [ 'a'<=C<='z' ]에 해당하지 않는다면, 이는 숫자, 공백, 특수 문자 등에 속하는 것.
2. 변환된 문자열 str1을 두 글자씩 쪼개 집합으로 만들어 주었다.
   • map을 사용하여 해당 글자 쌍이 str1에 몇 개 속하는지 카운트하였다.
   • 영문자로 이뤄진 글자 쌍만 카운트한다.
     • ex) aa1+aa2 -> map[aa]=2
     • 이렇게 만들어진 str1에 대한 집합의 크기를 len1으로 기록해 두었다.
3. 그리고, 변환된 문자열 str2를 마찬가지로 쪼갠다. 이번에는 str2의 집합의 원소들을 아까 생성한 map에서 빼준다.
   1. map값이 음수가 된다는 것은 해당 원소가 str1의 집합에 존재하지 않다는 것(혹은 개수가 부족)을 의미하므로 cnt++ 해준다. 
   2. str2에서 파생된 집합의 크기도 len2로 기록해준다.
4. 결과적으로, [ J({str1}, {str2}) = (len2-cnt)/(len1+cnt) ]이다.
5. answer = (len2-cnt)*65536/(len1+cnt)

 

 

소스 코드:

#include <string>
#include <map>

using namespace std;

map<string,int> m;
int solution(string str1, string str2) {
    int answer = 0;

    for(int i=0;i<str1.size();i++){ // 소문자로 변환
        if(str1[i]<'a') str1[i]=char(str1[i]-'A'+'a');
    }
    for(int i=0;i<str2.size();i++){ // 소문자로 변환
        if(str2[i]<'a') str2[i]=char(str2[i]-'A'+'a');
    }

    int len1=0,len2=0;
    for(int i=0;i<str1.size()-1;i++){
        string two = str1.substr(i,2);
        if('a'>two[0] ||two[0]>'z' || 'a'>two[1] ||two[1]>'z') continue;
        len1++;
        m[two]++;
    }
    
    int cnt=0;
    for(int i=0;i<str2.size()-1;i++){
        string two = str2.substr(i,2);
        if('a'>two[0] ||two[0]>'z' || 'a'>two[1] ||two[1]>'z') continue;
        len2++;
        m[two]--;
        if(m[two]<0) cnt++;
    }
    
    if(len1+cnt==0) answer=65536;
    else answer= (len2-cnt)*65536/(len1+cnt);
    
    return answer;
}