[Programmers] [1차] 뉴스 클러스터링

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

 

---

 

문제 해결 과정

착안

주어지는 두 개의 문자열에 대해 각각, 두 글자씩 끊어 읽었을 때 모두 알파벳으로 이루어져 있으면 끊어 읽은 문자열의 등장 횟수를 기록한다. 이때 두 개의 알파벳으로 이루어진 문자열이 등장하는 횟수 중 최솟값은 교집합에 해당하며, 최댓값은 합집합에 해당하는 값임에 착안하여 자카드 유사도를 계산한다.

 

구현

풀이 1) 두 글자씩 끊어 읽은 문자를 STL의 컨테이너를 활용해 기록하는 방법

각각 주어지는 문자열에 대해 std::unordered_map<string, int> 클래스의 컨테이너를 선언하여, 두 글자씩 끊어 읽었을 때 두 글자가 모두 알파벳이면 끊어 읽은 문자열의 등장 횟수를 컨테이너에 기록한다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

bool ischar(char c)
{
    if ('a' <= c && c <= 'z')
        return true;

    return false;
}

int solution(string str1, string str2)
{
    for (char& c : str1)
        c = tolower(c);

    for (char& c : str2)
        c = tolower(c);

    unordered_map<string, int> pairs1, pairs2;
    unordered_set<string> pairs;
    for (int i = 0; i < str1.size() - 1; i++)
        if (ischar(str1[i]) && ischar(str1[i + 1]))
        {
            pairs1[str1.substr(i, 2)]++;
            pairs.emplace(str1.substr(i, 2));
        }

    for (int i = 0; i < str2.size() - 1; i++)
        if (ischar(str2[i]) && ischar(str2[i + 1]))
        {
            pairs2[str2.substr(i, 2)]++;
            pairs.emplace(str2.substr(i, 2));
        }

    int a = 0, b = 0;
    for (auto& s : pairs)
    {
        a += min(pairs1[s], pairs2[s]);
        b += max(pairs1[s], pairs2[s]);
    }

    if (b)
        return int(float(a) / b * 65536);
    else
        return 65536;
}

 

풀이 2) 알파벳으로 이루어진 두 글자짜리 문자열의 종류가 676 개임에 착안하여 문제를 해결하는 방법

문제를 해결하고 나서 다른 분들의 풀이를 보다가 정말 똑똑한 풀이 방법을 알게 되어 포스트에 함께 남겨두려고 한다.

 

대소문자를 구분하지 않는다면 알파벳은 총 26 개의 문자의 집합으로 이루어져 있으므로 두 글자짜리 문자열은 총 676 개의 문자로 이루어져있다($\because 26 \times 26 = 676$). 이를 응용하면 해시(hash)의 개념과 같이 두 글자짜리 문자열을 서로 다른 문자열끼리 중복되지 않게 676 미만의 수로 변환할 수 있다는 점에 착안하여 문제를 해결할 수 있다.

 

한편, 문자 c에 저장되어 있는 문자가 알파벳이면 아래와 같이 tolower(), toupper() 함수를 사용하지 않고도 소문자 혹은 대문자로 표현이 가능하다.

• 소문자 표현: c & 31
• 대문자 표현: (c & 31) + 32

 

위의 방법을 응용하면 보다 더 간단하고 명료한 코드로도 문제를 해결할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <string>
#include <algorithm>

using namespace std;

int pairs1[676], pairs2[676];

int solution(string str1, string str2)
{
    for (int i = 0; i < str1.size() - 1; i++)
        if (isalpha(str1[i]) && isalpha(str1[i + 1]))
            pairs1[(str1[i] & 31) * 26 + (str1[i + 1] & 31)]++;
        
    for (int i = 0; i < str2.size() - 1; i++)
        if (isalpha(str2[i]) && isalpha(str2[i + 1]))
            pairs2[(str2[i] & 31) * 26 + (str2[i + 1] & 31)]++;
    
    int a = 0, b = 0;
    for (int i = 0; i < 676; i++)
    {
        a += min(pairs1[i], pairs2[i]);
        b += max(pairs1[i], pairs2[i]);
    }
    
    return b ? a * 65536 / b : 65536;
}

 

실행 결과