본문 바로가기
Programming Solve/프로그래머스

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

by msm1029 2022. 1. 26.
반응형

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42893

 

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

매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀

programmers.co.kr

 

문제 풀이

조건이 굉장히 많고 까다롭기 때문에 단계 별로 함수를 구현하여 풀이하였다.

1. 한 페이지 안에 알아야할 정보는 본인의 URL, 기본 점수, 외부 링크 수, 링크 점수, 매칭 점수가 있다. 이를 위해 구조체로 점수들을 모아놓은 scores 구현한다. 그리고 pair<string, scores> 로 page를 구현한다. string에는 본인의 URL이 들어있고 scores에는 점수가 모여있다.

//구조체 선언
typedef struct {
    int normalScore;
    int links;
    vector<string> linkPages;
    double linkScore;
    double matchingScore;
} scores;


//메인 함수에서 Page Pair 선언. first는 URL, second는 scores 구조체
vector<pair<string, scores> > pp; //page pair

2. 앞서 선언한 Page Pair를 완성하기 위해 본인의 URL을 구한다. 다음과 같이 함수로 구현하였다.

string url_parser(string str){
    string urlParser = "<meta property=\"og:url\" content=\"https://";
    string URL = "";
    int i = str.find(urlParser); //현재 인덱스는 '<' 의 위치가 저장되어있음
    i += urlParser.length(); // https:// 이후의 URL이 필요하므로 index 증가
    
    while(str[i] != '\"'){
        URL += str[i++];
    }
        
    return URL;
}

매개변수 str에는 페이지의 모든 정보가 들어있다. 해당 페이지에서 우리가 찾고 싶은 것은 메타 태그 안에 있는 본인의 URL이므로 urlParser라는 string에 찾을 문자열을 저장해두고 find 함수로 인덱스 i를 저장한다. 이 때, 인덱스는 문자열이 시작하는 '<'를 가리키고 있으므로 urlParser의 size만큼 더 증가시켜준다. 다음으로 URL이 끝나는 큰 따옴표가 나올 때까지 URL에 문자열을 추가하고 리턴한다.

 

3. 다음으로 기본 점수를 구하기 위해 body안에 포함되어 있는 word를 찾기 위해 아래와 같이 함수를 구현하였다.

int find_word(string str, string word){
    int cnt = 0; //찾은 word 개수
    string bs = "<body>"; //body start, body end
    string be = "</body>";
    
    int sp = str.find(bs); //starting point, end point
    sp += bs.size();
    
    int ep = str.find(be);
    
    str = str.substr(sp, ep-sp);
    transform(str.begin(), str.end(), str.begin(), ::tolower);
    transform(word.begin(), word.end(), word.begin(), ::tolower);
    string tmp = "";
    for(int i=0; i<str.size(); i++){
        if(isalpha(str[i]) == 0){ //알파벳이 아니라면 단어 확인
            if(tmp == word) cnt++;
            tmp = "";
        }
        else tmp += str[i];
    }
    
    return cnt;
}

body start 문자열과 body end 문자열을 find하여 앞선 방식과 같이 잘라낸다. 문제의 조건 중 대소문자의 구분을 하지 않는다고 하였으므로 transform 함수를 통해 모두 소문자로 변경해준다. 다음으로, 문자열 안에 word를 단어 단위로 찾아야 한다.

 

단어 단위가 무엇인지 알아보기 위해 예시를 살펴보면 검색어가 "aba" 일 때, "abab abababa"는 단어 단위로 일치 하는 것이 없으며 "aba@aba aba"는 단어 단위로 세개가 일치한다고 하였다. 따라서, 임시 문자열 tmp에 isalpha 함수를 통해 알파벳이면 tmp에 추가하다가 알파벳이 아니라면 단어를 확인하는 방식으로 기본 점수를 구한다.

4. 링크 수와 링크 점수를 구하기 위해 연결된 외부 링크를 모두 구해야한다. 이를 위해 아래의 함수를 구현하였다.

vector<string> find_links(string str){
    vector<string> links;
    string linkParser = "<a href=\"https://";
    int i = str.find(linkParser);
    
    while(i != str.npos){ // i != -1과 같은 표현, 찾으려는 문자열이 없을 때
        i += linkParser.size();
        string tmp = "";
        while(str[i] != '\"') tmp += str[i++];
        
        links.push_back(tmp);
        str = str.substr(i);
        i = str.find(linkParser);
    }
    
    return links;
}

앞서 URL을 구할 때의 방식과 비슷하지만 링크 수는 여러 개일 수 있으므로 while문이 하나 더 필요하다. npos는 -1의 값을 가지는 상수로, find 함수가 해당 문자열을 찾지 못했을 때 -1을 반환하게 된다. 즉, 링크를 더 이상 찾지 못할 때까지 반복한다.

 

링크를 구하는 방식은 URL을 구할 때와 비슷하다. 링크를 찾아 tmp 문자열을 links 벡터에 저장하고 해당 인덱스부터 다시 링크를 찾는 방식으로 반복한다. 과정이 끝나면 외부 링크들이 저장되어 있는 벡터를 리턴한다.

 

5. 이제 Page Pair를 위한 모든 과정이 끝났다. main 문에서 앞서 구현한 함수들로 구할 수 있는 본인의 URL, 기본 점수, 링크 수, 링크된 페이지를 Page Pair(pp)에 저장한 후 링크 점수와 매칭 점수를 구한다.

for(int i=0; i<pages.size(); i++){
        string ownURL = url_parser(pages[i]);
        scores tmp;
        tmp.normalScore = find_word(pages[i], word);
        tmp.linkPages = find_links(pages[i]);
        tmp.links = tmp.linkPages.size();
        pp.push_back(make_pair(ownURL, tmp));
    }
for(int i=0; i<pp.size(); i++){
        double tmp = 0.0;
        for(int j=0; j<pp.size(); j++){
            for(int k=0; k<pp[j].second.links; k++){
                if(pp[i].first == pp[j].second.linkPages[k]){
                    tmp += (double)pp[j].second.normalScore / pp[j].second.links;
                }
            }
        }
        
        pp[i].second.linkScore = tmp;
    }

링크 점수를 구하는 공식은 (나를 링크로 걸어 놓은 페이지의 기본점수 / 링크 수)이다.

pp[i]의 링크 점수를 구하기 위해 다른 모든 인덱스를 순회하며 링크를 확인해야 한다.

즉, pp[i].first(본인의 URL)과 pp[j].second.linkPages[k](다른 인덱스의 링크된 페이지들)를 비교하여 일치하면 기본 점수 공식을 통해 tmp에 추가한다.

 

double max = 0.0;
for(int i=0; i<pp.size(); i++){
    double tmp = pp[i].second.normalScore + pp[i].second.linkScore;
    if(max < tmp){
        max = tmp;
        answer = i;
    }
}

return answer;

매칭 점수의 공식은 더 간단하다. 임시 변수 tmp로 i번째 인덱스의 매칭 점수를 구하고 max값을 비교하여 매칭 점수가 가장 높은 인덱스를 answer에 할당하고 리턴하면 된다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

typedef struct {
    int normalScore;
    int links;
    vector<string> linkPages;
    double linkScore;
    double matchingScore;
} scores;

string url_parser(string str){
    string urlParser = "<meta property=\"og:url\" content=\"https://";
    string URL = "";
    int i = str.find(urlParser); //현재 인덱스는 '<' 의 위치가 저장되어있음
    i += urlParser.length(); // https:// 이후의 URL이 필요하므로 index 증가
    
    while(str[i] != '\"'){
        URL += str[i++];
    }
        
    return URL;
}

int find_word(string str, string word){
    int cnt = 0; //찾은 word 개수
    string bs = "<body>"; //body start, body end
    string be = "</body>";
    
    int sp = str.find(bs); //starting point, end point
    sp += bs.size();
    
    int ep = str.find(be);
    
    str = str.substr(sp, ep-sp);
    transform(str.begin(), str.end(), str.begin(), ::tolower);
    transform(word.begin(), word.end(), word.begin(), ::tolower);
    string tmp = "";
    for(int i=0; i<str.size(); i++){
        if(isalpha(str[i]) == 0){ //알파벳이 아니라면 단어 확인
            if(tmp == word) cnt++;
            tmp = "";
        }
        else tmp += str[i];
    }
    
    return cnt;
}

vector<string> find_links(string str){
    vector<string> links;
    string linkParser = "<a href=\"https://";
    int i = str.find(linkParser);
    
    while(i != str.npos){ // i != -1과 같은 표현, 찾으려는 문자열이 없을 때
        i += linkParser.size();
        string tmp = "";
        while(str[i] != '\"') tmp += str[i++];
        
        links.push_back(tmp);
        str = str.substr(i);
        i = str.find(linkParser);
    }
    
    return links;
}

int solution(string word, vector<string> pages) {
    int answer = 0;
    vector<pair<string, scores> > pp; //page pair
    
    for(int i=0; i<pages.size(); i++){
        string ownURL = url_parser(pages[i]);
        scores tmp;
        tmp.normalScore = find_word(pages[i], word);
        tmp.linkPages = find_links(pages[i]);
        tmp.links = tmp.linkPages.size();
        pp.push_back(make_pair(ownURL, tmp));
    }
    
    for(int i=0; i<pp.size(); i++){
        double tmp = 0.0;
        for(int j=0; j<pp.size(); j++){
            for(int k=0; k<pp[j].second.links; k++){
                if(pp[i].first == pp[j].second.linkPages[k]){
                    tmp += (double)pp[j].second.normalScore / pp[j].second.links;
                }
            }
        }
        
        pp[i].second.linkScore = tmp;
    }
    
    double max = 0.0;
    for(int i=0; i<pp.size(); i++){
        double tmp = pp[i].second.normalScore + pp[i].second.linkScore;
        if(max < tmp){
            max = tmp;
            answer = i;
        }
    }
    
    return answer;
}
반응형
저작자표시

'Programming Solve > 프로그래머스' 카테고리의 다른 글

프로그래머스 - 110 옮기기 / C++  (0) 2022.01.27
프로그래머스 - 불량 사용자 / C++  (0) 2022.01.26
프로그래머스 - 다트 게임 / C++  (0) 2022.01.26
프로그래머스 - 신고 결과 받기 / C++  (0) 2022.01.19
프로그래머스 - 땅따먹기 / C++  (0) 2021.11.21

관련글

티스토리툴바