[프로그래머스] 매칭점수 :: c++, 8번 테스트케이스, 풀이, 코드

By 희은w

Algorithm 문제/프로그래머스

2021. 1. 29. 11:09

매칭 점수

걸린 시간 : 3시간 이상

문제

난이도 ★★★☆☆

문제 설명

프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.

한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.

예를 들어, 다음과 같이 A, B, C 세 개의 웹페이지가 있고, 검색어가 hi라고 하자.

이때 A 웹페이지의 매칭점수는 다음과 같이 계산할 수 있다.

기본 점수는 각 웹페이지에서 hi가 등장한 횟수이다.
- A,B,C 웹페이지의 기본점수는 각각 1점, 4점, 9점이다.
외부 링크수는 다른 웹페이지로 링크가 걸린 개수이다.
- A,B,C 웹페이지의 외부 링크 수는 각각 1점, 2점, 3점이다.
A 웹페이지로 링크가 걸린 페이지는 B와 C가 있다.
- A 웹페이지의 링크점수는 B의 링크점수 2점(4 ÷ 2)과 C의 링크점수 3점(9 ÷ 3)을 더한 5점이 된다.
그러므로, A 웹페이지의 매칭점수는 기본점수 1점 + 링크점수 5점 = 6점이 된다.

검색어 word와 웹페이지의 HTML 목록인 pages가 주어졌을 때, 매칭점수가 가장 높은 웹페이지의 index를 구하라. 만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 구하라.

제한사항

pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고, 길이는 1 이상 20 이하이다.
한 웹페이지 문자열의 길이는 1 이상 1,500 이하이다.
웹페이지의 index는 pages 배열의 index와 같으며 0부터 시작한다.
한 웹페이지의 url은 HTML의태그 내에태그의 값으로 주어진다.
- 예를들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은 https://careers.kakao.com/index 이다.
한 웹페이지에서 모든 외부 링크는 <a href=

https://careers.kakao.com/index

>의 형태를 가진다.
- 내에 다른 attribute가 주어지는 경우는 없으며 항상 href로 연결할 사이트의 url만 포함된다.
- 위의 경우에서 해당 웹페이지는 https://careers.kakao.com/index 로 외부링크를 가지고 있다고 볼 수 있다.
모든 url은 https:// 로만 시작한다.
검색어 word는 하나의 영어 단어로만 주어지며 알파벳 소문자와 대문자로만 이루어져 있다.
word의 길이는 1 이상 12 이하이다.
검색어를 찾을 때, 대소문자 구분은 무시하고 찾는다.
- 예를들어 검색어가 blind일 때, HTML 내에 Blind라는 단어가 있거나, BLIND라는 단어가 있으면 두 경우 모두 해당된다.
검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영한다.
- 단어는 알파벳을 제외한 다른 모든 문자로 구분한다.
- 예를들어 검색어가 aba 일 때, abab abababa는 단어 단위로 일치하는게 없으니, 기본 점수는 0점이 된다.
- 만약 검색어가 aba 라면, aba@aba aba는 단어 단위로 세개가 일치하므로, 기본 점수는 3점이다.
결과를 돌려줄때, 동일한 매칭점수를 가진 웹페이지가 여러 개라면 그중 index 번호가 가장 작은 것를 리턴한다
- 즉, 웹페이지가 세개이고, 각각 매칭점수가 3,1,3 이라면 제일 적은 index 번호인 0을 리턴하면 된다.

코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

struct WebPage {
    int basePoint;
    vector<int> linkTo;
    int linkNum;
    double linkPoint;
    double matchingPoint;
    WebPage() {
        basePoint = 0;
        linkPoint = 0;
        linkNum = 0;
        matchingPoint = 0;
    }
};

int solution(string word, vector<string> pages) {
    int answer = 0;
    vector<WebPage*> webPages;
    for (int i = 0; i < pages.size(); i++) {
        webPages.push_back(new WebPage());
    }
    vector<string> address;
    transform(word.begin(), word.end(), word.begin(), ::tolower);

    for (int i = 0; i < pages.size(); i++) {
        string& s = pages[i];
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        // 해당 사이트의 url 저장
        int pos = 0, mid = 0, posr;
        while (mid <= pos) {
            pos = s.find("<meta", pos + 1);
            posr = s.find(">", pos);
            mid = s.rfind("https://", posr); // >에서 왼쪽으로 찾기
        }
        posr = s.find("\"", mid);
        string url = s.substr(mid, posr - mid);
        address.push_back(url);


        // body 내의 문자열 갯수 측정
        pos = s.find("<body>", posr);

        int start = pos;
        while (1) {
            start = s.find(word, start + 1);
            if (start == string::npos)
                break;
            if (!isalpha(s[start - 1]) && !isalpha(s[start + word.size()])) {
                webPages[i]->basePoint++;
                start += word.size();
            }
        }
    }

    for (int i = 0; i<pages.size(); i++) {
        string& s = pages[i];
        int posl = s.find("<body>");
        int mid = posl;
        int posr;

        while (1) {
            posl = s.find("<a href", posl + 1);
            if (posl == string::npos)
                break;
            webPages[i]->linkNum++;
            posl = s.find("https://", posl + 1);
            posr = s.find(">", posl);
            mid = s.rfind("\"", posr);

            if (mid <= posl)
                continue;

            string url = s.substr(posl, mid - posl);
            auto location = find(address.begin(), address.end(), url);
            if (location == address.end())
                continue;
            int idx = location - address.begin();
            auto linkvec = webPages[i]->linkTo;
            if (find(linkvec.begin(), linkvec.end(), idx) == linkvec.end()) // 없는 idx만 넣기
                webPages[i]->linkTo.push_back(idx);
        }
    }

    for (int i = 0; i < pages.size(); i++) {
        for (int j = 0; j < webPages[i]->linkTo.size(); j++) {
            int idx = webPages[i]->linkTo[j];
            webPages[idx]->linkPoint += (double)webPages[i]->basePoint / (double)webPages[i]->linkNum;
        }
    }

    double maxPoint = 0;
    for (int i = 0; i<pages.size(); i++) {
        webPages[i]->matchingPoint = webPages[i]->basePoint + webPages[i]->linkPoint;
        if (webPages[i]->matchingPoint > maxPoint) {
            maxPoint = webPages[i]->matchingPoint;
            answer = i;
        }
    }

    return answer;
}

풀이

모든 test case를 통과할 수 있도록 태그의 위치를 잘 검색해서 값을 뽑아내면 된다.

웹페이지의 meta 태그를 검사하여 해당 페이지의 url을 address vector에 저장한다.
웹페이지의 body에서 주어진 word와 일치하는 단어가 있는지 단어 별로 검사한다.
- 일치하는 단어가 있을 시 해당 단어 주위에 알파벳이 아닌 문자가 있어야 통과.
- word와 body 모두 소문자 혹은 대문자로 통일 시켜주어야 찾기 쉽다.
웹페이지의 body에서 a 태그를 찾아서 해당 페이지의 linkNum을 계산해준다.
웹페이지의 body에서 a 태그를 찾아서 외부 링크가 향하는 페이지의 linkPoint를 계산해준다.
- linkPoint는 기본점수와 링크 수가 필요하므로 바로 직전 linkNum을 계산해주는 프로세스와 함께 행할 수 없다.
basePoint와 linkPoint를 가지고 matchingPoint를 계산해준다.
matchingPoint가 가장 작은 웹페이지의 index를 return한다.
- matchingPoint의 최대를 구하는 식으로 동작하여 최대값이 갱신되면 해당 index를 answer에 저장

채점 결과

주요 사항

8번 테스트 케이스가 안 풀어지는 경우

meta tag에서 <> 사이에 https://가 들어가지 않는 경우
- 다른 meta tag를 찾아야한다.
point 계산을 float 형으로 한 경우
- double형으로 변경해주어야한다.

=> 8번 테케 때문에 오래 걸렸지만, 기본 구현도 2시간은 걸렸고 강의를 찾아보니 여러 간편한 문법을 깨닫게 되었다.

find 함수에서 2번째 매개변수로 시작 위치를 넘길 수 있다.
rfind 함수는 시작 위치에서 반대 방향으로 찾아준다.
transform(시작, 끝, 결과시작, 연산 함수) 로 쉽게 변경 가능하다.
- 연산함수에 ::toupper 또는 ::tolower 를 넣으면 대소문자 변경이 수월하다.

참고: https://www.youtube.com/watch?v=XmciZoxp18g

저작자표시 비영리 변경금지

'Algorithm 문제 > 프로그래머스' 카테고리의 다른 글

[카카오 블라인드 2021] 메뉴 리뉴얼 :: c++ 코드, 문제 해석, 필요 함수 (0)	2021.02.13
[카카오 블라인드 2021] 신규아이디 추천 :: string 사용 문제 (0)	2021.02.06
[프로그래머스] 길찾기게임 :: c++, 코드, 트리 (0)	2021.01.28
[프로그래머스] 블록 이동하기 :: c++, 코드, DFS 쓰면 안되는 이유, BFS (0)	2021.01.17
[프로그래머스] 외벽점검 :: 재귀, 메모이제이션, 코드, 결과 (0)	2021.01.11

Notice

Category

Recent Post

Popular Post

Comment

Tags

Visitor Counter