[Programmers] 뉴스 클러스터링

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

2018 KAKAO BLINE RECRUITMENT

---

구현 Simulation

[ 알고리즘풀이 ]

 

 1) 2글자씩 끊어서 둘다 알파벳인지 체크한다.

 2) 두 글자 다 알파벳이라면 소문자로 바꿔준 후, count 배열에 해당 케이스를 저장한다.

     count 배열은 [26][26] 으로 선언해 ['a' ~ 'z']['a' ~ 'z'] 모든 경우를 count 한다.

 3) count 배열을 순회하며 교집합은 count1, count2 배열의 min 값이 되고 합집합은 count1, count2 배열의 max 값이 된다.

 

[ 코드구현 C++ ]

include <string>
#include <algorithm>
using namespace std;
 
bool isAlphabet(char c) {
    if ('A' <= c && c <= 'Z') return true;
    if ('a' <= c && c <= 'z') return true;
    return false;
}
 
int solution(string str1, string str2) {
    int cnt1[26][26] = {}, cnt2[26][26] = {};
 
    for (int i = 0; i < str1.length() - 1; i++) {
        if (isAlphabet(str1[i]) && isAlphabet(str1[i + 1])) {
            if ('A' <= str1[i] && str1[i] <= 'Z') str1[i] = (str1[i] - 'A') + 'a';
            if ('A' <= str1[i + 1] && str1[i + 1] <= 'Z') str1[i + 1] = (str1[i + 1] - 'A') + 'a';
            cnt1[str1[i] - 'a'][str1[i + 1] - 'a']++;
        }
    }
 
    for (int i = 0; i < str2.length() - 1; i++) {
        if (isAlphabet(str2[i]) && isAlphabet(str2[i + 1])) {
            if ('A' <= str2[i] && str2[i] <= 'Z') str2[i] = (str2[i] - 'A') + 'a';
            if ('A' <= str2[i + 1] && str2[i + 1] <= 'Z') str2[i + 1] = (str2[i + 1] - 'A') + 'a';
            cnt2[str2[i] - 'a'][str2[i + 1] - 'a']++;
        }
    }
    int andSet = 0, orSet = 0;
    for (int i = 0; i < 26; i++)
        for (int j = 0; j < 26; j++) {
            andSet += min(cnt1[i][j], cnt2[i][j]);
            orSet += max(cnt1[i][j], cnt2[i][j]);
        }
    int answer;
    if (andSet == 0 && orSet == 0) answer = 65536;
    else answer = (andSet * 65536) / orSet;
    return answer;
}

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/Programmers/%5B1%EC%B0%A8%5D_%EB%89%B4%EC%8A%A4_%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0%EB%A7%81.cpp

travelbeeee/ProblemSolving

---