[String] 매칭 점수 - 2019 KAKAO BLIND RECRUITMENT

해결 방법

이 문제는 특별한 알고리즘을 요구하지는 않고, 문자열 파싱과 구현만 잘 해준다면 해결할 수 있다.

웹 페이지의 url은 meta 태그의 content 속성에 있다는 사실, 외부 링크는 a 태그의 href 속성에 있다는 사실, 그리고 단어는 알파벳을 제외한 다른 모든 문자로 구분한다는 사실을 잊지 말도록 하자.

구현 방식은 문제 설명에서 자세히 나와있으므로 이제 틀리기 쉬운 테스트케이스를 짚어보겠다.

 

<틀리기 쉬운 테스트 케이스>

- 링크점수 또는 매칭점수를 float형으로 두고 계산하면 테스트케이스 8번에서 막히기 쉽다. 정밀도(유효자릿수)가 더 높은 double형을 사용하자. float의 유효자릿수는 7이고, double의 유효자릿수는 15이다.

- 웹 페이지의 url을 추출하기 위해 "content="를 기준으로 찾는 경우에는 테스트케이스 9번에서 막히기 쉽다. 안전하게 아래와 같이 meta 부분까지 포함하여 기준을 잡아주자. 이 외에도 테스트케이스 9번에서 막힌다면 파싱 문제일 가능성이 높다.

search="<meta property=\"og:url\" content=";

- 소수점 연산 시 형변환을 하지 않은 경우에는 테스트케이스 17번에서 막히기 쉽다. 나눗셈 연산은 (double)로 형변환을 해주자.

 

 

소스코드

#include <string>
#include <vector>
#include <cmath>
#include <map>
using namespace std;

struct page {
    int wscore; // 기본 점수
    double lscore; // 링크 점수
    vector<string> links; // 외부 링크 목록
};

map<string, int> m; // 웹 페이지의 url은 별도의 (url, index) 쌍의 맵에 저장
vector<page> v(21);

bool is_alphabet(char c){
    int ic=(int)c;
    if((ic>=65&&ic<=90)||(ic>=97&&ic<=122)) return true;
    else return false;
}

// 문자열을 모두 소문자로 변환
string to_lower(string s){
    for(int i=0;i<s.length();i++){
        if(s[i]>=65&&s[i]<=90) s[i]+=32;
    }
    return s;
}

// 웹 페이지의 기본 점수 계산
int word_score(string keyword, string target){
    int cnt=0, pos=0, temp;
    keyword=to_lower(keyword);
    target=to_lower(target);
    while((temp=(int)target.find(keyword, pos))!=-1){
        if(temp==0) {
            if(!is_alphabet(target[keyword.length()])) cnt++;
        }
        else if(temp==target.length()-keyword.length()) {
            if(!is_alphabet(target[temp-1])) cnt++;
        }
        else if(!is_alphabet(target[temp+keyword.length()])&&!is_alphabet(target[temp-1])) cnt++;
        pos=temp+1;
    }
    return cnt;
}

int solution(string word, vector<string> pages) {
    int answer = 0;
    int start, end;
    string url, search;
    for(int i=0;i<pages.size();i++){
        // 웹 페이지의 url 추출 및 저장
        search="<meta property=\"og:url\" content=";
        start = (int)pages[i].find(search)+search.length()+1;
        end = pages[i].find("\"", start);
        url = pages[i].substr(start, end-start);
        m[url]=i;
        // 웹 페이지의 기본 점수 계산
        v[i].wscore=word_score(word, pages[i]);
        // 웹 페이지의 외부 링크 추출
        search="<a href=";
        int pos=0, temp;
        while((temp=(int)pages[i].find(search, pos))!=-1){
            start=temp+search.length()+1;
            end=pages[i].find("\"",start);
            url=pages[i].substr(start, end-start);
            v[i].links.push_back(url);
            pos=end+1;
        }
    }
    // 웹 페이지의 링크 점수 계산
    for(int i=0;i<pages.size();i++){
        for(int j=0;j<v[i].links.size();j++){
            if(m.count(v[i].links[j])) v[m[v[i].links[j]]].lscore+=(double)v[i].wscore/v[i].links.size();
        }
    }
    
    double maxi=0;
    for(int i=0;i<pages.size();i++){
        if(v[i].wscore+v[i].lscore>maxi){
            maxi=(double)v[i].wscore+v[i].lscore;
            answer=i;
        }
    }
    return answer;
}

 

 

테스트케이스 20개 모두 정답

 

+추가) Rabin-Karp 문자열 매칭 알고리즘을 적용한 word_score 함수 + hashcode 변환 함수

int hashcode(string s){
    int slen=s.length();
    int hcode=0;
    for(int i=0;i<slen;i++) hcode+=pow(2, slen-i-1)*s[i];
    return hcode;
}

// Rabin-Karp 문자열 매칭 알고리즘 사용
int word_score(string keyword, string target){
    keyword=to_lower(keyword);
    target=to_lower(target);
    int klen=keyword.length();
    int khcode=hashcode(keyword);
    int tlen=target.length();
    int thcode=hashcode(target.substr(0, klen));
    int cnt=0;
    if(klen>tlen) return 0;
    if(keyword==target.substr(0, klen)){
        if(klen==tlen) return 1;
        else if(!is_alphabet(target[klen])) cnt++;
    }
    for(int i=klen;i<tlen;i++){
        thcode=thcode*2-pow(2, klen)*(int)target[i-klen]+(int)target[i];
        if(khcode==thcode&&!is_alphabet(target[i-klen])){
            if(keyword!=target.substr(i-klen+1, keyword.length())) continue;
            if(i==tlen-1) cnt++;
            else if(!is_alphabet(target[i+1])) cnt++;
        }
    }
    return cnt;
}

 

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42893