[2019_KAKAO] 매칭 점수 (프로그래머스 레벨 3)

https://programmers.co.kr/learn/courses/30/lessons/42893?language=cpp

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

괴랄한 문자열 문제다.

조건이 많아서 abc가 word로 주어졌을 때

abca abcabc 가 page에 있다면 기본 점수를 0으로 해야 하는 것을 간과했으며,

기본 URL 확인시 단순 content 뒤에만 보도록 짰었는데 4줄과 같이 META를 정의하고 확인해줬어야 했다.

 

그래서 첫 번째 문제를 해결해 기본 점수 문제를 해결하고,

두 번째 문제를 해결해 기본 URL을 잘 찾을 수 있었다.

 

다소 조건이 까다로운 문제였지만, string의 문자열 함수를 이용해 잘 풀 수 있었다.

(문자열 함수 정리 : https://cpp-dev.tistory.com/56?category=852537)

 

또한 사용자 정의 sort 함수에 들어갈 정렬 기준의 응용도 할 수 있는 기회였다.

(사용자 정의 정렬 기준 : https://cpp-dev.tistory.com/88?category=852537)

 

그리고 find 함수로 찾고자 하는 문자열이 없는 경우 string::npos 를 반환하는 것을 알 수 있었다.

아래는 소스코드 전체다. 다른 사람들의 풀이와 비교했을 때 꽤 짧은 길이의 코드다.

 

#include <string>
#include <vector>
#include <algorithm>
#define META "<meta property=\"og:url\" content=\""
#define ENDURL "\"/>"
#define LINKSTART "<a href="
#define LINKEND "\">"
using namespace std;
bool cmp(pair<int, double> a, pair<int, double> b){
    // 앞에 인덱스, 뒤에 점수라면
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}
int solution(string word, vector<string> pages) {
    vector<string> URL;
    vector<double> BasePoint(pages.size(), 0), LinkPoint(pages.size(), 0);
    vector<vector<string> > OutLinks(pages.size());
 
    int toLower = 'a' - 'A';
    for (int i = 0; i<pages.size(); i++){
        for (int j = 0; j<pages[i].length(); j++){
            if ('A' <= pages[i][j] && pages[i][j] <= 'Z'){
                pages[i][j] += toLower;
            }
        }
    }
    for (int i = 0; i<word.length(); i++){
        if ('A' <= word[i] && word[i] <= 'Z') word[i] += toLower;
    }
    // 1. 기본점수
    for (int i = 0; i<pages.size(); i++){
        int index = 0;
        int cnt = 0;
        while (pages[i].find(word, index) != string::npos){
            int ele = pages[i].find(word, index);
            char next = pages[i][ele + word.length()];
            char before = pages[i][ele - 1];
            if (!('a' <= next && next <= 'z') && !('a' <= before && before <= 'z')) {
                cnt++; 
            }
            index = ele + 1;
        }
        BasePoint[i] = cnt;
    }
    // 2. URL 찾기
    for (int i = 0; i<pages.size(); i++){
        int url_start = pages[i].find(META, 0) + 33;
        int url_end = pages[i].find(ENDURL, url_start)-1;
        URL.push_back(pages[i].substr(url_start, url_end - url_start + 1));
    }
    // 연관 URL 찾기
    for (int i = 0; i<pages.size(); i++){
        int idx = 0;
        while (pages[i].find(LINKSTART, idx) != string::npos){
            int url_start = pages[i].find(LINKSTART, idx) + 9;
            int url_end = pages[i].find(LINKEND, url_start)-1;
            OutLinks[i].push_back(pages[i].substr(url_start, url_end - url_start + 1));
            idx = url_end + 1;
        }
    }
    vector<int> OutLinksNum(pages.size(), 0);
    for (int i = 0; i<OutLinks.size(); i++){
        OutLinksNum[i] = OutLinks[i].size();
    }
    
    for (int i = 0; i<pages.size(); i++){
        string cur_URL = URL[i];
        for (int j = 0; j<OutLinks.size(); j++){
            if (i == j) continue;
            if (OutLinks[j].size() == 0) continue;
            for (int k = 0; k<OutLinks[j].size(); k++){
                if (OutLinks[j][k].compare(cur_URL) == 0){
                    LinkPoint[i] = LinkPoint[i] + (double)(BasePoint[j] / OutLinksNum[j]);
                    break;
                }
            }
        }
    }
    vector<pair<int, double> > Result;
    for (int i = 0; i<pages.size(); i++){
        Result.push_back(make_pair(i, BasePoint[i] + LinkPoint[i]));
    }
    sort(Result.begin(), Result.end(), cmp);
    int answer = Result[0].first;
    return answer;
}