프로그래머스 - 매칭 점수 [C++]

이 문제는 문자열, 구현 문제이다.

 

주요 포인트는 대소문자 구별 X, 알파벳을 제외한 모든 문자가 구분자가 되는 단어들 파싱, 내 링크 및 외부 링크 찾기이다.

 

대소문자 구별을 하지 않는 방법은 전부 대문자나 소문자로 바꿔놓는 것이다. 이는 간단하게 구현할 수 있다.

 

알파벳을 제외한 모든 문자가 구분자가 되는 단어들을 파싱하기 위해 for문을 돌리면서 'a' <= c && c <= 'z' 를 체크하고, 아닌 경우에는 지금까지 쌓여있던 단어를 리턴 벡터에 저장하는 방식으로 구현했다.

 

내 링크 및 외부 링크 찾기는 kmp 알고리즘을 사용하여 속도를 높였다. 여기서 주의할 점은 단순히 "http://" 를 찾으면 오답이 나오게 되고, 태그까지 정확히 걸어서 "<a href=\"" 를 검색하게 만들어야 한다. 이 또한 kmp 알고리즘을 외우고만 있으면 쉽게 구현할 수 있다.

 

위 세 가지를 제외한 부수적인 부분들은 쉽게 구현할 수 있고, 이 요구사항들을 구현만 하면 정답이 나오게 된다.

#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <map>
using namespace std;

char toLower(char c)
{
    if ('A' <= c && c <= 'Z')
    {
        return c + ('a' - 'A');
    }
    else
    {
        return c;
    }
}

vector<string> split(string input)
{
    vector<string> result;
    string temp = "";
    for (char c : input)
    {
        if ('a' <= c && c <= 'z')
        {
            temp += c;
        }
        else
        {
            if (!temp.empty())
            {
                result.push_back(temp);
            }
            temp = "";
        }
    }
    if (!temp.empty())
    {
        result.push_back(temp);
    }
    return result;
}

vector<int> getPi(string comp)
{
    int m = comp.size();
    vector<int> pi(m, 0);
    int start = 1;
    int matched = 0;
    while (start + matched < m)
    {
        if (comp[start + matched] == comp[matched])
        {
            matched++;
            pi[start + matched - 1] = matched;
        }
        else
        {
            if (matched == 0)
            {
                start++;
            }
            else
            {
                start += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}

vector<int> kmp(string all, string comp)
{
    int n = all.size();
    int m = comp.size();
    vector<int> pi = getPi(comp);
    vector<int> result;
    int start = 0;
    int matched = 0;
    while (start <= n - m)
    {
        if (matched < m && all[start + matched] == comp[matched])
        {
            matched++;
            if (matched == m)
            {
                result.push_back(start);
            }
        }
        else
        {
            if (matched == 0)
            {
                start++;
            }
            else
            {
                start += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return result;
}

string getUrl(int index, string& page)
{
    string result = "";
    for (int i = index; page[i] != '\"'; i++)
    {
        result += page[i];
    }
    return result;
}

struct Node
{
    string url = "";
    int base = 0;
    int outer = 0;
    double link = 0;
    double matching = 0;
};
    
map<string, int> urlToIndex;
map<string, vector<int>> links;
vector<Node> nodes;

string getMyUrl(string page)
{
    vector<int> urlIndex = kmp(page, "<meta property=\"og:url\" content=\"");
    string myUrl = getUrl(urlIndex[0] + 33, page);
    return myUrl;
}

int calculateBase(string page, string word)
{
    vector<string> words = split(page);
    int base = 0;
    for (string& w : words)
    {
        if (w == word)
        {
            base++;
        }
    }
    return base;
}

int calculateOuter(string page, int me)
{
    vector<int> urlIndex = kmp(page, "<a href=\"");
    int outer = urlIndex.size();
    for (int i = 0; i < urlIndex.size(); i++)
    {
        string url = getUrl(urlIndex[i] + 9, page);
        links[url].push_back(me);
    }
    return outer;
}

void allLower(string& word)
{
    for (int i = 0; i < word.size(); i++)
    {
        word[i] = toLower(word[i]);
    }
}

int solution(string word, vector<string> pages) 
{   
    int answer = 0;
    allLower(word);
    
    for (int i = 0; i < pages.size(); i++)
    {
        string& page = pages[i];
        allLower(page);
        string myUrl = getMyUrl(page);
        urlToIndex[myUrl] = i;
        int base = calculateBase(page, word);
        int outer = calculateOuter(page, i);
        nodes.push_back({myUrl, base, outer, 0, 0});
    }
    
    double maxValue = -1;
    for (int i = 0; i < pages.size(); i++)
    {
        Node presentNode = nodes[i];
        string myUrl = presentNode.url;
        double linkScore = 0;
        
        for (int link : links[myUrl])
        {
            Node nextNode = nodes[link];
            linkScore += (double)(nextNode.base) / (nextNode.outer);
        }
        if (maxValue < linkScore + presentNode.base)
        {
            maxValue = linkScore + presentNode.base;
            answer = i;
        }
    }
    
    return answer;
}