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

Notice

Recent Posts

Recent Comments

Link

Tags more

Archives

Today

Total

관리 메뉴

Hello Ocean! 🌼

[프로그래머스/C++] 매칭 점수 본문

Algorithm

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

bba_dda 2021. 2. 3. 12:20

문제 설명

주어진 검색어에 대한 웹 페이지의 매칭점수를 계산해서, 매칭점수가 가장 큰 웹 페이지의 인덱스 구하기

만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 구하기

각 페이지별로 4 가지의 점수를 계산할 수 있다.

기본 점수 : 웹 페이지에서 검색어가 등장하는 횟수 (대소문자 무시)
외부 링크 수 : 해당 페이지에 존재하는, 다른 페이지로 걸린 링크의 수
링크 점수 : [해당 페이지(A)의 링크가 존재하는 다른 페이지(B)의 기본 점수 / B의 외부 링크 수]의 총합
매칭 점수 : 기본 점수 + 링크 점수

예를 들어, 다음과 같이 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점이 된다.

제한사항

pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고, 길이는1이상20이하이다.
한 웹페이지 문자열의 길이는1이상1,500이하이다.
웹페이지의 index는 pages 배열의 index와 같으며 0부터 시작한다.
한 웹페이지의 url은 HTML의태그 내에태그의 값으로 주어진다.
- 예를들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은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을 리턴하면 된다.

입출력 예 #1

word : blind
pages :

"<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>"

pages는 다음과 같이 3개의 웹페이지에 해당하는 HTML 문자열이 순서대로 들어있다.

Blind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. Link to b

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

Ut condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind Link to a

위의 예를 가지고 각각의 점수를 계산해보자.

기본점수 및 외부 링크수는 아래와 같다.
- a.com의 기본점수는 3, 외부 링크 수는 1개
- b.com의 기본점수는 1, 외부 링크 수는 2개
- c.com의 기본점수는 1, 외부 링크 수는 1개
링크점수는 아래와 같다.
- a.com의 링크점수는 b.com으로부터 0.5점, c.com으로부터 1점
- b.com의 링크점수는 a.com으로부터 3점
- c.com의 링크점수는 b.com으로부터 0.5점
각 웹 페이지의 매칭 점수는 다음과 같다.
- a.com : 4.5 점
- b.com : 4 점
- c.com : 1.5 점

따라서 매칭점수가 제일 높은 첫번째 웹 페이지의 index인 0을 리턴 하면 된다.

풀이

pages 길이만큼 loop를 돌면서,
1. 모든 문자를 소문자로 바꾸기
2. 각 page의 url 찾아 저장하기
3. 각 page의 기본 점수 계산
4. 각 page에 존재하는 외부 link 찾아 저장해두기
pages.size() 크기의 match_score vector 만들기. -> 초기값 : 각 페이지의 기본 점수(1에서 계산)
pages 길이만큼 loop를 돌면서,
1. 1-4에서 찾은 외부 link 페이지에게, 이 페이지의 기본점수 나누어주기 (기본 점수/외부 링크 수)
match_score에서 값이 가장 큰 인덱스 찾아 return

첫 번째 코드

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

using namespace std;

bool isAlphabet(char c) { //기본점수 계산시 단어 파악을 위한 함수
    if (c == -1) //맨 끝 단어일경우.. 
        return true;
    if ((c>='A' && c<='Z')||(c>='a' && c<='z'))
        return true;
    else
        return false;
}
int solution(string word, vector<string> pages) {
    int answer = 0;
    vector<int> basic_score(pages.size(), 0);
    vector<string> url(pages.size());
    vector<vector<string>> link(pages.size());
    vector<vector<int>> link_index(pages.size());

    transform(word.begin(), word.end(), word.begin(), ::tolower);
    for (int i = 0;i < pages.size();i++) {
        //모두 소문자로 바꾸기 
        transform(pages[i].begin(), pages[i].end(), pages[i].begin(), ::tolower);

        //해당 페이지의 url 찾기 
        string url_flag = "content=\"";
        int url_start = pages[i].find(url_flag, 0);
        url_start += url_flag.size();
        int url_end = pages[i].find("\"", url_start);
        url[i] = pages[i].substr(url_start, url_end - url_start);

        //기본 점수 계산 
        int found = pages[i].find(word, 0); //못 찾으면 found=-1
        while (found > 0) {
            char front = pages[i][found - 1];
            char back;
            if (found + word.size() >= pages[i].size())
                back = -100;
            else
                back = pages[i][found + word.size()];
            if (!isAlphabet(front) && !isAlphabet(back))
                basic_score[i]++;
            found = pages[i].find(word, found + word.size());
        }

        //해당 페이지에 존재하는 외부 링크 찾기 
        string link_flag = "<a href=\"";
        found = pages[i].find(link_flag, 0); //못 찾으면 -1
        while (found > 0) {
            int link_start = found + link_flag.size();
            int link_end = pages[i].find("\">", link_start);
            if (link_end != -1) {
                link[i].push_back(pages[i].substr(link_start, link_end - link_start));
            }
            found = pages[i].find(link_flag, link_end);
        }
    }
    vector<double> match_score(basic_score.begin(),basic_score.end());
    for (int i = 0;i < pages.size();i++) {
        int link_num = link[i].size();
        for (int j = 0;j < link_num;j++) {
            if (find(url.begin(), url.end(), link[i][j]) != url.end()) {
                //페이지i에 존재하는 외부 링크 페이지들에게 i의 기본 점수 나누어주기 
                int index = distance(url.begin(), find(url.begin(), url.end(), link[i][j]));
                match_score[index] += basic_score[i] / (double)link_num;
                link_index[i].push_back(index);
            }
        }
    }
    answer = max_element(match_score.begin(), match_score.end())- match_score.begin();
    return answer;
}

제출 결과

오답 이유

programmers.co.kr/questions/9548

page의 url을 찾을 때, 이전에는 앞에 content=\"가 존재하는 부분을 찾았었는데,

질문하기를 보니, 앞에 정확히 <meta property=\"og:url\" content=\"https://로 시작하는 부분만 url로 사용해야 한다고 해서, 이를 수정하였다.

정답 코드

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


using namespace std;

bool isAlphabet(char c) {
    if (c == -1) //맨 끝 단어일경우.. 
        return true;
    if ((c>='A' && c<='Z')||(c>='a' && c<='z'))
        return true;
    else
        return false;
}
int solution(string word, vector<string> pages) {
    int answer = 0;
    vector<int> basic_score(pages.size(), 0);
    vector<string> url(pages.size());
    vector<vector<string>> link(pages.size());
    vector<vector<int>> link_index(pages.size());

    transform(word.begin(), word.end(), word.begin(), ::tolower);
    for (int i = 0;i < pages.size();i++) {
        //모두 소문자로 바꾸기 
        transform(pages[i].begin(), pages[i].end(), pages[i].begin(), ::tolower);

        //해당 페이지의 url 찾기 
        string content = "<meta property=\"og:url\" content=\"";
        string url_flag = "<meta property=\"og:url\" content=\"https://";
        int meta = pages[i].find("<meta", 0);
        int url_start = pages[i].find(url_flag, meta);
        url_start += content.size();
        int url_end = pages[i].find("\"", url_start);
        url[i] = pages[i].substr(url_start, url_end - url_start);

        //기본 점수 계산 
        int found = pages[i].find(word, 0); //못 찾으면 found=-1
        while (found > 0) {
            char front = pages[i][found - 1];
            char back;
            if (found + word.size() >= pages[i].size())
                back = -100;
            else
                back = pages[i][found + word.size()];
            if (!isAlphabet(front) && !isAlphabet(back))
                basic_score[i]++;
            found = pages[i].find(word, found + word.size());
        }

        //해당 페이지에 존재하는 외부 링크 찾기 
        string link_flag = "<a href=\"";
        found = pages[i].find(link_flag, 0); //못 찾으면 -1
        while (found > 0) {
            int link_start = found + link_flag.size();
            int link_end = pages[i].find("\">", link_start);
            if (link_end != -1) {
                link[i].push_back(pages[i].substr(link_start, link_end - link_start));
            }
            found = pages[i].find(link_flag, link_end);
        }
    }
    vector<double> match_score(basic_score.begin(),basic_score.end());
    for (int i = 0;i < pages.size();i++) {
        int link_num = link[i].size();
        for (int j = 0;j < link_num;j++) {
            if (find(url.begin(), url.end(), link[i][j]) != url.end()) {
                //페이지i에 존재하는 외부 링크 페이지들에게 i의 기본 점수 나누어주기 
                int index = distance(url.begin(), find(url.begin(), url.end(), link[i][j]));
                match_score[index] += basic_score[i] / (double)link_num;
                link_index[i].push_back(index);
            }
        }
    }
    answer = max_element(match_score.begin(), match_score.end())- match_score.begin();
    return answer;
}

제출 결과

정답은 나왔지만, 질문하기를 보니 "정규표현식" 사용을 의도한 문제라는 생각이 들었다.

참고

코드에서 문자를 모두 소문자로 바꾸기 위해 transform()를 이용하였는데,
visual studio에서는 transform(word.begin(), word.end(), word.begin(), tolower); 가 잘 돌아갔는데
프로그래머스에 제출하자 이 부분에서 오류가 났다.

transform()내의 tolower 앞에 :: 붙이자 오류가 해결되었다
(transform(word.begin(), word.end(), word.begin(), ::tolower);)

이 오류와 ::표시에 대해 찾아보았다.

stackoverflow.com/questions/5539249/why-cant-transforms-begin-s-end-s-begin-tolower-be-complied-successfu

위의 링크에 따르면,
transform(word.begin(), word.end(), word.begin(), [](const unsigned char i){ return tolower(i); });가 정확한 표현이라고 한다.

tolower()가 여러개 overload되어서 여러개중에 정확히 어떤 것인지를 명시해주지 않아서 발생한 오류라고 하고,

앞에 ::을 붙이거나, [](const unsigned char i){ return tolower(i); } 해서 오류를 해결한다고 하는데..

~~사실 저 링크에서 정확히 무슨 얘기를 하는건지 아직 다 못알아들었다~~

TO-DO

정규 표현식 공부하기

'Algorithm' 카테고리의 다른 글

[백준/C++] 1175. 배달 (0)	2021.02.26
[프로그래머스/C++] 신규 아이디 추천 (0)	2021.02.08
[C++] struct와 class의 차이 (0)	2021.01.25
[프로그래머스/C++] 길 찾기 게임 (0)	2021.01.25
[C++/프로그래머스] 블록 이동하기 (0)	2021.01.18

'Algorithm' Related Articles

Hello Ocean! 🌼

[프로그래머스/C++] 매칭 점수 본문

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

문제 설명

제한사항

입출력 예 #1

풀이

첫 번째 코드

제출 결과

오답 이유

정답 코드

제출 결과

참고

TO-DO

'Algorithm' 카테고리의 다른 글

티스토리툴바