[C++로 풀이] 매칭 점수⭐⭐⭐

Date: 2021.03.25 Updated: 2021.03.25

📌 매칭 점수

난이도 ⭐⭐⭐

🚀 문제

["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://a.com\"/>\n</head>  \n<body>\nBlind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. \n<a href=\"https://b.com\"> Link to b </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://b.com\"/>\n</head>  \n<body>\nSuspendisse potenti. Vivamus venenatis tellus non turpis bibendum, \n<a href=\"https://a.com\"> Link to a </a>\nblind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.\n<a href=\"https://c.com\"> Link to c </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://c.com\"/>\n</head>  \n<body>\nUt condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind\n<a href=\"https://a.com\"> Link to a </a>\n</body>\n</html>"]

["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://careers.kakao.com/interview/list\"/>\n</head>  \n<body>\n<a href=\"https://programmers.co.kr/learn/courses/4673\"></a>#!MuziMuzi!)jayg07con&&\n\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://www.kakaocorp.com\"/>\n</head>  \n<body>\ncon%\tmuzI92apeach&2<a href=\"https://hashcode.co.kr/tos\"></a>\n\n\t^\n</body>\n</html>"]

🚀 내 풀이 ⭕

문제에서 요구한대로 구현만 하면 되는 문제라 어렵진 않았지만 그만큼 챙겨야할 조건들이 많아 까다로운 문제이기도 했다. 코드도 짱 길다..

#include <string>
#include <vector>

using namespace std;

/* 한 페이지의 데이터 */
struct Data {
    string my_url; // 이 페이지의 링크
    vector<string> link; // 이 페이지의 외부 링크들
    string text; // 이 페이지의 텍스트들 (HTML 문법 제외 <Body>태그 안에 있는 일반 텍스트)
};

/* 한 페이지의 점수 */
struct Score {
    int basic;       // 기본점수
    int outer_link;  // 외부링크 수
    double link;     // 링크점수
    double matching; // 매칭점수
};

int solution(string word, vector<string> pages) {
    int answer = 0;
    vector<Data> data(pages.size());    // 페이지들 별로 데이터(링크, 외부링크, 텍스트)를 담을 배열
    vector<Score> scores(pages.size()); // 페이지들 별로 4가지 종류의 점수를 담을 배열

    for (int i = 0; i < word.length(); ++i)
        word[i] = tolower(word[i]); // 대소문자 구분하지 않으니 word 도 모두 소문자로 변환

    /* 이 페이지의 링크 저장 */
    const string mlink1 = "<meta property=\"og:url\" content=\"https://";
    const string mlink2 = "\"";
    for (int i = 0; i < pages.size(); ++i) {
        int start = pages[i].find(mlink1);
        int end = pages[i].find(mlink2, start + mlink1.length());
        int len = end - (start + mlink1.length());
        data[i].my_url = pages[i].substr(start + mlink1.length(), len);
    }

    /* 이 페이지의 외부 링크들 저장 */
    const string olink1 = "<a href=\"https://";
    const string olink2 = "\">";
    for (int i = 0; i < pages.size(); ++i) {
        int start = 0;
        int end = 0;
        while (true) {
            start = pages[i].find(olink1, end + olink2.length());
            if (start == string::npos) break;
            end = pages[i].find(olink2, start + olink1.length());
            int len = end - (start + olink1.length());
            data[i].link.push_back(pages[i].substr(start + olink1.length(), len));
        }
    }

    /* 이 페이지의 텍스트들 저장 */
    const string body_start = "<body>";
    const string body_end = "</body>";
    for (int i = 0; i < pages.size(); ++i) {
        int start = pages[i].find(body_start);
        int end = pages[i].find(body_end);
        int len = end - (start + body_start.length());
        string body = pages[i].substr(start + body_start.length(), len);
        
        bool aTag = false;
        string str = "";
        for (int j = 0; j < body.length(); ++j) {
            if (body[j] == '<') {
                aTag = true;
                continue;
            }
            if (body[j] == '>') {
                aTag = false;
                continue;
            }
            if (aTag == false)
                str += body[j];
        }

        data[i].text = str;
    }

    /* 1. 기본 점수 구하기 */
    for (int i = 0; i < data.size(); ++i) {

        // 대문자는 소문자로 바꾸고 알파벳이 아닌 문자는 모두 공백으로 
        for (int j = 0; j < data[i].text.length(); ++j) {
            if (data[i].text[j] >= 'A' && data[i].text[j] <= 'Z')
                data[i].text[j] = tolower(data[i].text[j]);
            if (data[i].text[j] >= 'a' && data[i].text[j] <= 'z')
                continue;
            data[i].text[j] = ' ';
        }

        // 공백을 기준으로, 즉 단어 단위로 파싱하여 벡터에 저장
        vector<string> v_temp;
        string temp = "";
        for (int j = 0; j < data[i].text.length(); ++j) {
            if (data[i].text[j] == ' ') {
                v_temp.push_back(temp);
                temp = "";
                continue;
            }
            temp += data[i].text[j];
        }
        v_temp.push_back(temp); // 이거 안해주면 마지막 단어는 벡터에 추가되지 않는다! (공백 만날때만 추가하게 해놔가지고..)

        // 기본점수 카운팅
        scores[i].basic = 0.0;
        for (int j = 0; j < v_temp.size(); ++j)
            if (v_temp[j] == word)
                scores[i].basic++;
    }

    /* 2. 외부 링크 수 구하기 */ 
    for (int i = 0; i < data.size(); ++i) 
        scores[i].outer_link = data[i].link.size();
    
    /* 3. 링크 점수 구하기 */
    for (int i = 0; i < data.size(); ++i) {
        scores[i].link = 0.0;
        for (int j = 0; j < data.size(); ++j) {
            for (int k = 0; k < data[j].link.size(); ++k) {
                if (data[i].my_url == data[j].link[k])
                    scores[i].link += (double)scores[j].basic / scores[j].outer_link;
            }
        }
    }

    /* 4. 매칭 점수 구하기 (+ 최대 매칭 점수)*/
    double max = 0.0;
    for (int i = 0; i < data.size(); ++i) {
        scores[i].matching = scores[i].basic + scores[i].link;
        if (max < scores[i].matching) {
            max = scores[i].matching;
            answer = i;
        }
    }
    
    return answer;
}

🔥 전처리 단계

1️⃣ word 소문자로 변환

    for (int i = 0; i < word.length(); ++i)
        word[i] = tolower(word[i]);

검색어는 대소문자를 무시하고 찾기 때문에 검색어 word 또한 모두 소문자로 변환해주어야 한다. “Hello”는 “hello”가 될 수 있도록!

2️⃣ 페이지 별 “링크” 저장 (+테스트케이스 9번 에러 이유)

    /* 이 페이지의 링크 저장 */
    const string mlink1 = "<meta property=\"og:url\" content=\"https://";
    const string mlink2 = "\"";
    for (int i = 0; i < pages.size(); ++i) {
        int start = pages[i].find(mlink1);
        int end = pages[i].find(mlink2, start + mlink1.length());
        int len = end - (start + mlink1.length());
        data[i].my_url = pages[i].substr(start + mlink1.length(), len);
    }

start : “<meta property="og:url" content="https://” 의 시작 위치를 담을 변수
- 이 문자열의 처음 문자인 meta 태그를 여는 < 의 인덱스가 담기게 된다.
end : “\"”의 시작 위치를 담을 변수 (즉 주소의 닫는 따옴표의 위치)
- 처음엔 “"/>” 의 위치를 찾도록 하였는데 이러니까 테스트케이스 9번만 틀렸다. 왜냐하면 meta 태그에 다른 속성들이 또 있을 수 있기 때문이다. 예를 들어 "<meta property=\"og:url\" content=\"https://" hello = hello 이렇게 링크 뒤에 다른 속성이 더 붙을 수도 있는 것이다. 즉 content 속성이 꼭 meta 태그의 마지막에 위치하리란 법은 없다. 따라서 pages[i].find(mlink2, start + mlink1.length()) 즉, 링크 주소의 시작 위치 이후부터 주소를 끝맺을 때 등장하는 따옴표 \" 를 찾게끔만 해주면 된다. (\"은 많이 등장하기 때문에 start처럼 찾는 범위를 pages[i] 전체 범위로 하면 안된다.
  - 이렇게 9번만 틀리던 것을 해결하였다. (질문하기 탭에서 어떤 고마운 분께서 남겨주신 조언이였다.ㅠㅠㅠ)
len : 링크 주소의 길이
- 링크 주소 문자열만 substr 함수로 추출할건데 이 함수는 부분 문자열의 길이를 파라미터로 요구하기 때문에 링크 주소의 길이를 구해주었다.
  - 링크의 시작 위치 : start + mlink1.length()
  - 링크의 끝 위치 : end

3️⃣ 페이지 별 “외부링크”들 저장

    /* 이 페이지의 외부 링크들 저장 */
    const string olink1 = "<a href=\"https://";
    const string olink2 = "\">";
    for (int i = 0; i < pages.size(); ++i) {
        int start = 0;
        int end = 0;
        while (true) {
            start = pages[i].find(olink1, end + olink2.length());
            if (start == string::npos) break;
            end = pages[i].find(olink2, start + olink1.length());
            int len = end - (start + olink1.length());
            data[i].link.push_back(pages[i].substr(start + olink1.length(), len));
        }
    }

외부 링크는 여러개가 있을 수 있다. 따라서 "<a href=\"https://" 가 더 이상 없을 떄까지 while 문 내에서 계속 외부링크를 찾는다.(a href 태그) 외부 링크 문자열들을 link 벡터에 차례로 저장한다.

난 처음에 외부 링크를 저장하는 컨테이너를 vector가 아닌 해시맵(unordered_set)을 썼었다. unordered_set은 중복을 자동으로 제거해주는데, 사실 동일한 사이트의 외부 링크가 여러개일 수도 있다. 즉, 한 페이지에 a.com 링크가 여러번 등장할 수도 있는 것이다. 그럼 외부링크도 여러개일텐데, 해시맵을 사용하면 a.com가 한번 등장했다는 것으로 처리되므로 외부링크 수가 1 개로 처리될 수 있다. 이런 생각이 들어서 vector 로 컨테이너를 바꾸었다.

4️⃣ 페이지 별 “텍스트”들 저장

    /* 이 페이지의 텍스트들 저장 */
    const string body_start = "<body>";
    const string body_end = "</body>";
    for (int i = 0; i < pages.size(); ++i) {
        int start = pages[i].find(body_start);
        int end = pages[i].find(body_end);
        int len = end - (start + body_start.length());
        string body = pages[i].substr(start + body_start.length(), len);
        
        bool aTag = false;
        string str = "";
        for (int j = 0; j < body.length(); ++j) {
            if (body[j] == '<') {
                aTag = true;
                continue;
            }
            if (body[j] == '>') {
                aTag = false;
                continue;
            }
            if (aTag == false)
                str += body[j];
        }

        data[i].text = str;
    }

<body>
Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum, 
<a href="https://a.com"> Link to a </a>
blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.
<a href="https://c.com"> Link to c </a>
</body>

위 텍스트는 “Link to a”, “Link to c” 까지 포함하여, “Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum, Link to a blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut. Link to c” 가 되야 한다. <a href="https://a.com">와 <a href="https://c.com">는 검색어 탐색 범위가 되지 못한다.

텍스트는 <body> 태그 안에 있다.
<a> 태그의 속성값들은 검색어 찾는 범위가 되지 못한다.
- <a href="https://a.com">와 <a href="https://c.com">는 검색어 탐색 범위가 안디ㅏ.
1️⃣ 텍스트는 <body> 태그 안에 있으므로 <body>의 시작 위치와 끝을 찾는다.
- start 시작 위치, end 끝 위치, len는 <body> 태그 안에 있는 모든 텍스트의 길이
- 최종적으로 body에 <body> 태그 내부에 있는 텍스트들이 담기게 한다.
  - 일단 <a href="https://a.com">와 <a href="https://c.com">도 포함되어있긴 한 상태. 이제 이건 텍스트가 아닌걸로 걸러내야 한다.
2️⃣ 외부링크 <a href>, </a> 태그는 텍스트에서 제외
- < 문자가 등장하면 a 태그가 시작되었다고 판단하고 str에 문자를 덧붙이지 않기 위해 플래그 상태를 바꿈.(aTag)
  - <a href의 <던, </a>의 <던 둘 다 해당
- > 문자가 등장하면 a 태그가 끝났다고 판단하고 이제 str에 문자를 덧붙이기 위해 플래그를 상태를 바꿈 (aTag)
  - <a href의 >던, </a>의 >던 둘 다 해당
- 최종적으로 str에 “Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum, Link to a blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut. Link to c” 가 담긴다.

🔥 점수 구하기

1️⃣ 기본 점수

    /* 1. 기본 점수 구하기 */
    for (int i = 0; i < data.size(); ++i) {

        // 대문자는 소문자로 바꾸고 알파벳이 아닌 문자는 모두 공백으로 바꾸기
        for (int j = 0; j < data[i].text.length(); ++j) {
            if (data[i].text[j] >= 'A' && data[i].text[j] <= 'Z')
                data[i].text[j] = tolower(data[i].text[j]);
            if (data[i].text[j] >= 'a' && data[i].text[j] <= 'z')
                continue;
            data[i].text[j] = ' ';
        }

        // 공백을 기준으로, 즉 단어 단위로 파싱하여 벡터에 저장
        vector<string> v_temp;
        string temp = "";
        for (int j = 0; j < data[i].text.length(); ++j) {
            if (data[i].text[j] == ' ') {
                v_temp.push_back(temp);
                temp = "";
                continue;
            }
            temp += data[i].text[j];
        }
        v_temp.push_back(temp); // 이거 안해주면 마지막 단어는 벡터에 추가되지 않는다! (공백 만날때만 추가하게 해놔가지고..)

        // 기본점수 카운팅
        scores[i].basic = 0.0;
        for (int j = 0; j < v_temp.size(); ++j)
            if (v_temp[j] == word)
                scores[i].basic++;
    }

기본 점수는 검색어가 포함된 횟수이다. 근데 검색어 포함 기준은 “단어 기준”이며, 단순 공백 기준 뿐만 아니라 그냥 알파벳이 아닌 문자가 사이에 있으면 단어라고 판단된다. “abc@abc” 는 “abc” 단어가 2 개 있는 것으로 판단된다.

전처리의 4️⃣과정에서 추출한 “텍스트” 에서 검색어 찾기

대소문자 구분 안하므로 먼저 대문자는 소문자로 변환
알파벳이 아닌건 모두 공백으로 변환
공백을 기준으로 단어로 파싱하여 임시 벡터에 단어별로 저장해둔다.
이 임시 벡터에서 검색어 word와 일치하는 단어를 찾는다. 찾았다면 점수 1씩 증가

2️⃣ 외부링크 수

    /* 2. 외부 링크 수 구하기 */ 
    for (int i = 0; i < data.size(); ++i) 
        scores[i].outer_link = data[i].link.size();

간단하게, 페이지별로 외부링크들을 벡터에 저장해두었으므로 벡터의 사이즈만 대입해주면 됨.

3️⃣ 링크 점수

    /* 3. 링크 점수 구하기 */
    for (int i = 0; i < data.size(); ++i) {
        scores[i].link = 0.0;
        for (int j = 0; j < data.size(); ++j) {
            for (int k = 0; k < data[j].link.size(); ++k) {
                if (data[i].my_url == data[j].link[k])
                    scores[i].link += (double)scores[j].basic / scores[j].outer_link;
            }
        }
    }

나눗셈 과정에서 소수점이 발생할 수 있으므로 double로 선언하였다. data[i] 페이지의 링크(my_url)가 다른 모든 페이지들의 외부 링크 페이지들에 속해있나 보고 연산하면 된다. 입력 크기가 적어서(최대 20개에 문자열 길이 최대 1500자) 시간초과 안나고 연산시간도 나쁘지 않았다. 입력 크기가 더 커진다면 이렇게 구하면 안될듯 하다.

4️⃣ 매칭 점수

    double max = 0.0;
    for (int i = 0; i < data.size(); ++i) {
        scores[i].matching = scores[i].basic + scores[i].link; // 매칭점수 = 기본점수 + 링크점수
        if (max < scores[i].matching) {
            max = scores[i].matching;
            answer = i;
        }
    }

정답 인덱스 answer에 저장!

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Hyunsang(Harry) Cho 🧸⚽🥩