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

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/42893

제한사항

• 생략…

---

풀이

2시간 이상
(문제를 풀다가 멈추고 다시 풀어서 시간이 조금 애매했다.)
처음에는 html 문자열을 개행 문자로 나누어 문자열처리를 하려고 했는데, 생각보다 문제가 애매하게 느껴졌다.

1. 참조하는 URL을 찾을 때, “<a href=”https://” 를 기준으로 찾아도 되는 것 일까? body 내부의 text에서도 해당 문자열이 나타날 수 있지 않나?
2. 문제 조건 중 “한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)” -> body 태그 내부의 텍스트만 해당 웹페이지의 텍스트인가? 다른 태그에서 나타나는 검색어는 무시해도 되는가?

엣지 케이스를 생각할수록 점점 머리가 복잡해져서, 그냥 일단 무식하게 풀게 되었다.
편의를 위해 모두 대문자로 바꾸고, 페이지의 URL과 참조하는 URL을 찾아낸뒤, 점수를 합산하는 방식으로 풀었다.

제출후 8번, 17번 테스트케이스에서 실패했는데, 최댓값을 찾을 때

int max_val = -1;

자료형을 int로 하여 정보가 손실되는 문제였다.

코드

// 07:30 ~
#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

string toupper(string s){
    for(int i =0; i < s.size(); ++i){
        if(s[i] >= 'a' && s[i] <= 'z'){
            s[i] = 'A' + s[i] - 'a';
        }
    }
    return s;
}

bool is_alpha(char c){
    if(c >= 'A' && c <= 'Z') return true;
    return false;
}

int solution(string word, vector<string> pages) {
    map<string,vector<string>> refered;
    vector<string> urls(pages.size());
    vector<int> out_refer(pages.size(), 0);
    vector<double> scores(pages.size(), 0);
    map<string,double> link_score;
    
    word = toupper(word);
    
    for(int i =0; i < pages.size(); ++i){
        // 대문자 전체 변환
        string page = toupper(pages[i]);
        // self url 탐색
        string self_url_start = toupper("<meta property=\"og:url\" content=\"https://");
        string self_url;
        for(int j = page.find(self_url_start) + self_url_start.length(); page[j] != '\"'; ++j){
            self_url += page[j];
        }
        urls[i] = self_url;
        
        // refer url 탐색
        string refer_url_start = toupper("<a href=\"https://");
        int start_idx = 0;
        while(true){
            int j = page.find(refer_url_start, start_idx);
            if(j == -1) break;
            string refer_url;
            for(j = j + refer_url_start.length(); page[j] != '\"'; ++j){
                refer_url += page[j];
            }
            out_refer[i] += 1;
            refered[refer_url].push_back(urls[i]);
            start_idx = j;
        }
        
        // word matching 탐색
        int cnt = 0;
        start_idx = 0;
        while(true){
            int j = page.find(word, start_idx);
            if(j == -1) break;
            // 한 단어일 때
            if(j + word.length() != page.length() && !is_alpha(page[j + word.length()])){
                cnt += 1;
            }
            start_idx = j + word.length() + 1;
        }
        scores[i] += cnt;
    }
    // self 링크점수 도출
    for(int i =0; i < urls.size(); ++i){
        link_score[urls[i]] = scores[i] / out_refer[i];
    }
    
    // 매칭점수 도출
    int max_idx = -1;
    double max_val = -1;
    for(int i =0; i < urls.size(); ++i){
        string url = urls[i];
        if(refered.find(url) != refered.end()){
            for(string refer_url : refered[url]){
                cout << refer_url;
                scores[i] += link_score[refer_url];
            }
        }
        if(scores[i] > max_val){
            max_idx = i;
            max_val = scores[i];
        }
    }
    return max_idx;
}