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

2019 카카오 채용 코딩 테스트 문제입니다.

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

문제 확인

 

스트링 처리 문제입니다.

 

풀이

 

정규 표현식을 사용하여 푸는 것이 푸는 시간 단축에 도움이 됩니다. c++의 <regex>를 사용해 풀어봅니다.

씹어먹는 C++ - <17 - 2. C++ 정규 표현식() 라이브러리 소개>

regex::optimize를 이용하여 성능 개선을 할 수 있습니다.

 

웹사이트 이름 처리 : <meta [^>]*content=\"https://(\\S*)\"[^>]*/>

[^>]* : 어트리뷰트 content가 나오기 이전에 '>'가 나오면 무시합니다.

https://(\\S*)\" : () 캡처를 통해 웹사이트 이름을 받아옵니다.

 

word 기본 점수 처리 : [^a-z](" + word + "[^a-z])+

[^a-z] : word 앞에 다른 알파벳이 오지 않도록 합니다.

(" + word + "[^a-z])+ : 단어 단위로 word를 캡처하며 해당 문자열에서 (문자열 길이 - 1)/(word 길이 + 1)를 통해 다수의 word가 겹쳐서 나온 경우를 처리합니다.

 

링크 점수 처리 : <a[\\s]*href=\"https://(\\S*)\"[\\s]*>

(\\S*) : 링크 주소를 받아와 해당 웹페이지가 기록한 웹페이지에 존재한다면 링크 점수를 반영합니다.

 

코드

#include <string>
#include <vector>
#include <map>
#include <regex>
using namespace std;
 
typedef struct page {
    double basic, link;
}page;
 
 
int solution(string word, vector<string> pages) {
    int wlen = word.length(), n = pages.size();
 
    regex re_pname("<meta [^>]*content=\"https://(\\S*)\"[^>]*/>", regex::icase | regex::optimize);
    regex    re_href("<a[\\s]*href=\"https://(\\S*)\"[\\s]*>", regex::icase | regex::optimize);
    regex    re_word("[^a-z](" + word + "[^a-z])+", regex::icase | regex::optimize);
    smatch mch;
 
 
    map<string, int> mp;//주소 : 인덱스
    page pg[20] = { 0 };
 
    auto e = sregex_iterator();
    for (int i = 0; i < n; ++i) {
        regex_search(pages[i], mch, re_pname);
        mp[mch[1].str()] = i;
 
        auto s = sregex_iterator(pages[i].begin(), pages[i].end(), re_word);//basic
        while (s != e) {
            pg[i].basic += (s->str().length() - 1) / (wlen + 1);
            ++s;
 
        }
    }
 
    for (int i = 0; i < n; i++) {
        auto s = sregex_iterator(pages[i].begin(), pages[i].end(), re_href);//link
        int dv = distance(s, e);
        while (s != e) {
            auto t = mp.find((*s)[1].str());//링크된 웹사이트가 기록되어 있으면
            if (t != mp.end())
                pg[t->second].link += pg[i].basic / dv;
            ++s;
        }
 
    }
 
    double mx = pg[0].basic + pg[0].link;//최댓값 찾기
    int mx_idx = 0;
    for (int i = 1; i < n; i++) {
        if (pg[i].basic + pg[i].link > mx) {
            mx = pg[i].basic + pg[i].link;
            mx_idx = i;
        }
    }
 
    return mx_idx;
}