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

매칭점수 (Level 3)

문제

전체 문제 보기

코딩테스트 연습 - 매칭 점수

접근법

문제의 요구사항이 상당히 많고 문자열 추출, 탐색 등의 활용이 많이 필요한 문제입니다. C++을 활용하여 문자열을 처리해야 한다면 더욱 까다롭게 느껴질 수 있습니다. 실제 코딩 테스트에서 이러한 유형을 풀기 위해서는 요구사항을 정확히 파악하여 빠르게 구현하는 능력이 필요해 보입니다. 문제에서 요구하는 기능이 많지만, 각각 요구사항들 자체의 난이도는 높지 않기 때문에 하나씩 차근차근 구현해 보도록 하겠습니다.

구현

문자열 처리 함수

문제에서 요구한 기능들 중 문자열을 처리하는 다음 두 가지 기능을 함수로 구현하였습니다.

• string ToSmall(string& str): 문제에서는 대소문자 구분을 하지않는다고 하였습니다. 모든 html 문자열과 word를 소문자로 변환하기 위해서 사용됩니다.
• string GetWord(const string& str, int& pos): 문제에서는 검색어는 단어 단위로 비교하며, 단어는 알파벳을 제외한 다른 모든 문자로 구분한다고 하였습니다. 그래서 입력받은 str의 pos 위치에서부터 하나의 단어만 추출하여 반환하는 함수가 필요했습니다. 그리고 전달받은 pos는 참조로 받아서 반환한 단어의 다음 글자를 가리킬 수 있도록 설계하였습니다.

위 두 함수는 다음과 같이 구현하였습니다.

// 입력받은 문자열을 모두 소문자로 변환
void ToSmall(string& str)
{
    const int diff = 'A' - 'a';
    for(char& c : str)
        if('A' <= c && c <= 'Z')
            c -= diff;
}
// str[pos] 부터 하나의 알파벳 단어 추출. 
string GetWord(const string& str, int& pos)
{
    string retval;
    if(pos >= str.size()) return retval;

    while(pos < str.size())
    {
        if('a' <= str[pos] && str[pos] <= 'z')
        {
            retval += str[pos];
            pos++;

        }else //특수문자를 만나면 break
            break;
    }
    // str이 특수문자로 시작한 경우
    if(retval.size() == 0)
    {
            retval += str[pos];
            pos++;
    }
    return retval;
}

PagesMap

각 페이지들은 고유의 URL을 가집니다. 그리고 각 페이지는 외부 참조링크를 가질 수 있습니다. 우리는 링크를 통해서 해당 페이지에 접근할 수 있는 자료구조가 필요합니다. 이때 사용할 수 있는 자료구조로는 map,과 unordered_map이 있습니다. string 타입을 고려했을 때 상황에 따라서 map이 유리한 경우가 있고 unordered_map이 유리한 경우가 있습니다. 이번 풀이에서는 map을 사용하였습니다. 그래서 PagesMap은 다음과 같이 정의하였습니다.

using PagesMap = map<string, class PageInfo*>;

PagesMap의 사용방법은 다음과 같습니다.

• PageInfo를 초기화하는 과정에서 Page의 URL을 추출하여 PagesMap에 URL과 PageInfo의 주소값을 등록.
• 링크 점수를 계산시 링크가 PagesMap에 등록 되었는지 확인. 등록되었다면, 해당 PageInfo의 Matching Point에 Link Point를 더해준다.

PagesMap은 전역 변수로 선언하기보다는 지역변수로 선언한 후 모든 PageInfo 클래스에서 사용할 수 있도록 PageInfo의 생성자에 인자로 전달하는 의존성 주입 기법을 활용하여 모든 PageInfo 객체가 단일한 PagesMap을 참조하도록 하였습니다.

PageInfo의 속성

각 페이지들이 가져야하는 속성은 다음과 같습니다.

• &mPagesMap: PagesMap의 참조. 생성자에서 의존성 주입 기법으로 모든 PageInfo 객체가 동일한 PagesMap을 참조 받음. 해당 페이지의 URL을 등록하고 외부 참조 중인 페이지의 포인터 변수를 가져오기 위해서 사용됨.
• mIndex: 해당 페이지의 인덱스 번호(생성시 입력 받음)
• mHtml : 해당 페이지의 html 문자열(생성 시 move 함수로 이전 받음)
• mBasicPoint: 해당 페이지의 기본 점수(CalBasicPoint 메서드에서 계산됨)
• mMatchingPoint: 해당 페이지의 매칭 점수(CalBasicPoint 메서드와, 타 PageInfo 객체에서 호출하는 CalLinkPoint 함수에서 계산됨)
• mLinks: 해당 페이지가 참조하고 있는 다른 페이지의 포인터 배열 (AddExternalLinks 메서드에서 추가됨)

PageInfo::RegisterURL

RegisterURL 메서드는 생성자에서 호출되며, mHtml 문자열에서 자신의 URL을 탐색한 뒤 &mPagesMap에 등록하는 역할을 담당합니다.

void PageInfo::RegisterURL()
{    
    // URL 추출
    string meta_str("<meta property=\"og:url\" content=\"https://");
    int start_pos = mHtml.find(meta_str);
    start_pos += meta_str.size();
    int end_pos = mHtml.find("\"/>", start_pos);
    string URL(mHtml, start_pos, end_pos - start_pos);
    // 추출한 URL을 map에 등록
    mPagesMap[URL] = this;    
}

PageInfo::AddExternalLinks

AddExternalLinks 메서드는 클라이언트 측(Solution 함수)에서 호출되며, mHtml 문자열에서 외부 링크를 탐색합니다. 그리고 탐색한 외부 링크가 &mPagesMap에 등록되어있는지 확인합니다. 등록되어 있는 외부 링크라면 등록되어있는 PageInfo의 주소 값을 저장하고 등록되지 않은 링크라면 nullptr을 저장합니다.

void PageInfo::AddExternalLinks()
{
    string a_str("<a href=\"https://");
    int start_pos{};
    while((start_pos = mHtml.find(a_str, start_pos)) != string::npos)
    {
        start_pos += a_str.size();
        int end_pos = mHtml.find("\">", start_pos);
        string URL(mHtml, start_pos, end_pos - start_pos);
        auto iter = mPagesMap.find(URL);
        if(iter != mPagesMap.end())
        {
            // Pages Map에 등록된 링크라면 해당 링크의 주소를 mLinks 배열에 저장
            mLinks.push_back(iter->second);
        }
        else
        {
            // Pages Map에 등록되지 않은 링크는 mLinks 배열에 nullptr로 저장
            mLinks.push_back(nullptr);
        }
    }
}

PageInfo::CalBasicPoint

CalBasicPoint 메서드는 기본 점수를 계산하는 함수입니다. mHtml에 검색 대상인 target 단어가 몇 번 들어있는지 탐색하여 탐색된 문자열 개수만큼 mBasicPoint에 더해줍니다. 이때 단어의 구분 기준은 "알파벳을 제외한 다른 모든 문자로 구분한다."로 문제에서 제시되었습니다. 그래서 앞서 구현하였던 GetWord 함수를 사용해서 mHtml에서 단어를 가져옵니다.

void PageInfo::CalBasicPoint(const string& target)
{
    int pos{};
    string word;
    while((word = GetWord(mHtml, pos)) != "")
    {
        if(word == target)// word를 발견한 경우
            mBasicPoint++;
    }
    mMatchingPoint += (double) mBasicPoint;
}

PageInfo::CalLinkPoint

CalLinkPoint 메서드는 링크 점수를 계산하는 함수입니다. 링크 점수는 해당 페이지의 (기본점수) / (링크된 페이지 수)로 계산합니다. mLinks 배열에는 외부로 연결된 페이지들의 주소 값이 들어있습니다. 이를 활용하여서 링크 점수를 해당 페이지의 매칭점수에 다음과 같이 더해줄 수 있습니다.

void PageInfo::CalLinkPoint()
{
    double linkPoint = (double) mBasicPoint / (double) mLinks.size();
    for(PageInfo* link : mLinks)
    {
        if(link != nullptr)
        {
            //cout << mIdx << "가 " <<link->mIdx << "에 링크점수 " << linkPoint << "점 추가 "<< endl; 
            link->AddMatchingPoint(linkPoint);
        }
    }
}

전체 소스 코드

위 내용들을 바탕으로 다음과 같이 구현할 수 있습니다.

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
using PagesMap = map<string, class PageInfo*>;

// 입력받은 문자열을 모두 소문자로 변환
void ToSmall(string& str)
{
    const int diff = 'A' - 'a';
    for(char& c : str)
        if('A' <= c && c <= 'Z')
            c -= diff;
}
// str[pos] 부터 하나의 알파벳 단어 추출. 
string GetWord(const string& str, int& pos)
{
    string retval;
    if(pos >= str.size()) return retval;

    while(pos < str.size())
    {
        if('a' <= str[pos] && str[pos] <= 'z')
        {
            retval += str[pos];
            pos++;

        }else //특수문자를 만나면 break
            break;
    }
    // str이 특수문자로 시작한 경우
    if(retval.size() == 0)
    {
            retval += str[pos];
            pos++;
    }
    return retval;
}
class PageInfo{
public:
    PageInfo(PagesMap& pages_map, string page, int idx);
    void AddExternalLinks();
    void CalBasicPoint(const string& target);
    void CalLinkPoint();
    int GetIndex() const {return mIdx;}
    double GetMatchingPoint() const {return mMatchingPoint;}
private:
    // method
    void RegisterURL();
    void AddMatchingPoint(double amount) {mMatchingPoint += amount;}

    // attributes
    PagesMap& mPagesMap;
    string mHtml;
    int mIdx{};
    int mBasicPoint{};
    double mMatchingPoint{};
    vector<PageInfo*> mLinks{};

};
PageInfo::PageInfo(PagesMap& pages_map, string page, int idx) 
    : mPagesMap(pages_map), mHtml(move(page)), mIdx(idx)
{
    RegisterURL();
}

void PageInfo::CalLinkPoint()
{
    double linkPoint = (double) mBasicPoint / (double) mLinks.size();
    for(PageInfo* link : mLinks)
    {
        if(link != nullptr)
        {
            //cout << mIdx << "가 " <<link->mIdx << "에 링크점수 " << linkPoint << "점 추가 "<< endl; 
            link->AddMatchingPoint(linkPoint);
        }
    }
}
void PageInfo::AddExternalLinks()
{
    string a_str("<a href=\"https://");
    int start_pos{};
    while((start_pos = mHtml.find(a_str, start_pos)) != string::npos)
    {
        start_pos += a_str.size();
        int end_pos = mHtml.find("\">", start_pos);
        string URL(mHtml, start_pos, end_pos - start_pos);
        auto iter = mPagesMap.find(URL);
        if(iter != mPagesMap.end())
        {
            // Pages Map에 등록된 링크라면 해당 링크의 주소를 mLinks 배열에 저장
            mLinks.push_back(iter->second);
        }
        else
        {
            // Pages Map에 등록되지 않은 링크는 mLinks 배열에 nullptr로 저장
            mLinks.push_back(nullptr);
        }
    }
}
void PageInfo::RegisterURL()
{    
    // URL 추출
    string meta_str("<meta property=\"og:url\" content=\"https://");
    int start_pos = mHtml.find(meta_str);
    start_pos += meta_str.size();
    int end_pos = mHtml.find("\"/>", start_pos);
    string URL(mHtml, start_pos, end_pos - start_pos);
    // 추출한 URL을 map에 등록
    mPagesMap[URL] = this;    
}
void PageInfo::CalBasicPoint(const string& target)
{
    int pos{};
    string word;
    while((word = GetWord(mHtml, pos)) != "")
    {
        if(word == target)// word를 발견한 경우
            mBasicPoint++;
    }
    mMatchingPoint += (double) mBasicPoint;
    //cout << mBasicPoint << endl;
}
int solution(string word, vector<string> pages) {
    int answer = 0;
    PagesMap pages_map;
    // 주어진 입력을 모두 소문자로 변환
    ToSmall(word);
    for(string& html : pages)
        ToSmall(html);

    // PageInfo 생성
    vector<PageInfo> page_infos;
    page_infos.reserve(pages.size());
    for(int i = 0 ; i < pages.size(); ++i)
    {
        page_infos.emplace_back(pages_map, move(pages[i]), i);
    }

    for(auto& info : page_infos)
    {
        // 외부링크 연결
        info.AddExternalLinks();
    }
    for(auto& info : page_infos)
    {
        // 기본 점수 계산
        info.CalBasicPoint(word);
        // 링크 점수 계산
        info.CalLinkPoint();
    }

    auto comp = [](const PageInfo& lhs, const PageInfo& rhs)
    {
        if(lhs.GetMatchingPoint() < rhs.GetMatchingPoint()) return true;
        else if(lhs.GetMatchingPoint() == rhs.GetMatchingPoint() &&
               lhs.GetIndex() > rhs.GetIndex()) return true;
        else return false;
    };
    auto iter = max_element(page_infos.begin(), page_infos.end(), comp);
    answer = iter->GetIndex();
    return answer;
}

실행결과