[2019 KAKAO BLIND RECRUITMENT] 매칭 점수(C++)

https://www.welcomekakao.com/learn/courses/30/lessons/42893#qna

코딩테스트 연습 - 매칭 점수 | 프로그래머스

이번 문제는, 간단한 구현 문제이다.

 

---

 

문제의 조건을 읽고, 차례로 구현을 한다면 쉽게 풀 수 있다.

 

하지만, strtok를 사용해서 문제를 풀어야 한다고 생각했다면 틀린 생각이다.

주어지는 pages들이 항상 \n을 사용해서 구분되어 있지 않기 때문이다.

 

아마 55점이 나왔다면, strtok를 사용해서 문제를 풀었기 때문이다.

 

---

 

이번 문제를 통해서 배울 수 있는 것은, 예제뿐만 아니라 전체 테스트 케이스를 커버할 수 있는 코드를 생각하는 것이 중요하다. 문제의 조건에서, \n을 통해서 HTML 문서를 작성했다고 하지 않았다.

 

 

웹 페이지를 순환하며 URL을 모두 기록한다. 외부 링크에 대한 점수 계산은 모든 웹 페이지 URL과 a href의 URL을 수집한 후에 진행해야 한다. 실시간으로 계산을 할 수 없다. 이유는 생각해보면 당연하다.

 

 

단어 찾기는, 웹 페이지를 하나씩 처리하면서 진행해도 무관하다.

 

 

이 2가지 방식을 베이스로 코드를 작성한다면 쉽게 해결 할 수 있다.

 

---

 

문제 코드(C++)

#include <string>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
 
using namespace std;
 
bool cmp(pair<double, double> p1, pair<double, double> p2) {
    if (p1.first == p2.first)
        return p1.second < p2.second;
    else
        return p1.first > p2.first;
}
 
string make_lowercase(string s) {
    for (int i = 0; i < s.length(); i++) {
        if (s.at(i) >= 'A' && s.at(i) <= 'Z') {
            s.at(i) += 32;
        }
    }
    return s;
}
 
int solution(string word, vector<string> pages) {
    int answer = 0;
    double score[20] = { 0 };
    double result[20] = { 0 };
    map<string, int> url_map;
    set<string> url_v[20];
 
    word = make_lowercase(word);
    vector<pair<double, double>> v;
 
    for (int i = 0; i < pages.size(); i++) 
    {
        string str = pages.at(i);
        string meta = "<meta";
        string https = "\"https://";
        string https_end = "\"";
        string a = "<a href=\"";
        string a_end = "\"";
        
        // Find URL
        size_t found = 0;
        while (true) {
            found = str.find(meta, found);
            if (found == string::npos)
                break;
 
            string temp = str.substr(found + meta.length());
            temp = temp.substr(0, temp.find(">"));
 
            found += meta.length();
            if (temp.find(https) != string::npos) {
                size_t found = temp.find(https_end, temp.find(https) + https.length());
                temp = temp.substr(temp.find(https) + 1, found - 1 - temp.find(https));
                url_map[temp] = i;
            }
        }
 
        // Find a href
        found = 0;
        while (true) {
            found = str.find(a, found);
            if (found == string::npos)
                break;
 
            string temp = str.substr(found + a.length());
            temp = temp.substr(0, temp.find("\">"));
 
            found += a.length();
            url_v[i].insert(temp);
        }
 
        // Find a word
        str = make_lowercase(str);
        found = str.find(word, 0);
        while (found != string::npos) {
            score[i] += 1;
            if ((found >= 1 && str.at(found - 1) >= 'a' && str.at(found - 1) <= 'z') ||
                (found + word.length() < str.length() - 1 && str.at(found + word.length()) >= 'a' && str.at(found + word.length()) <= 'z')) {
                score[i] -= 1;
            }
 
            found = str.find(word, found + word.length());
        }
    }
 
    // a href scoring
    for (int i = 0; i < pages.size(); i++) {
        if (url_v[i].size() == 0)
            continue;
 
        double temp = score[i] / url_v[i].size();
        for (set<string>::iterator it = url_v[i].begin(); it != url_v[i].end(); it++) {
            if (url_map.count((*it)) == 0)
                continue;
            result[url_map[(*it)]] += temp;
        }
    }
 
    // Sorting
    for (int i = 0; i < pages.size(); i++) {
        cout << score[i] + result[i]<< endl;
        v.push_back(make_pair(result[i] + score[i], i));
    }
 
    sort(v.begin(), v.end(), cmp);
    answer = v.at(0).second;
    cout << answer << endl;
 
    return answer;
}