티스토리 뷰

PS/프로그래머스

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

땡욱 2020. 8. 28. 09:58

문제설명은 더보기를 눌러주세요

더보기

매칭 점수

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

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

예를 들어, 다음과 같이 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의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.
  • 한 웹페이지에서 모든 외부 링크는 <a href=https://careers.kakao.com/index>의 형태를 가진다.
    • <a> 내에 다른 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을 리턴 하면 된다.

입출력 예 #2

#!MuziMuzi!)jayg07con&&

con% muzI92apeach&2 ^

  • 기본점수 및 외부 링크수는 아래와 같다.

    • careers.kakao.com/interview/list 의 기본점수는 0, 외부 링크 수는 1개
    • www.kakaocorp.com 의 기본점수는 1, 외부 링크 수는 1개

  • 링크점수는 아래와 같다.

    • careers.kakao.com/interview/list 의 링크점수는 0점
    • www.kakaocorp.com 의 링크점수는 0점

  • 각 웹 페이지의 매칭 점수는 다음과 같다.

    • careers.kakao.com/interview/list : 0점
    • www.kakaocorp.com : 1 점

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

 

-풀이-

1. 그냥 string 관련 구현하는 문제입니다. (알고리즘 필요 X)

2. 처음엔 코드를 복잡하게 짰고, 그 코드로 낑낑대다가 9번 테스트를 끝까지 통과하지 못해서 갈아엎었습니다.

3. tip을 드리자면 linkTag, contentTag, httpTag와 같이 string을 지정해놓고
    find()로 찾는것이 코드가 훨씬 깔끔해집니다. (이 부분은 테스트 9, 10번과도 연관이 있는 듯 합니다)

5. 17번 테스트가 통과되지 않는다면 double형을 사용해야 합니다. (float사용결과 통과 X)

 

-코드-

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int getLinkNum(int idx, string page, int N);
int getBasicScore(string word, string page);
string getPageName(string page);
bool isAlpha(char A);
int basicScore[20], linkNum[20];
double matchScore[20];
string pageName[20];
vector<int> link[20];
int solution(string word, vector<string> pages) {
    int answer = 0;
    
    for(int i=0; i<pages.size(); i++){ 
        pageName[i] = getPageName(pages[i]); //페이지 이름
        basicScore[i] = getBasicScore(word, pages[i]); // 기본점수
    }
    for(int i=0; i<pages.size(); i++){ 
        linkNum[i] = getLinkNum(i, pages[i], pages.size()); // 링크구하기
    }
    
    double maxScore = 0.0;
    for(int i=0; i<pages.size(); i++){ // 매칭점수 구하기
        matchScore[i] = (double)basicScore[i];
        for(int j=0; j<link[i].size(); j++){
            matchScore[i] += ((double)basicScore[link[i][j]] / linkNum[link[i][j]]);
        }
        if(maxScore < matchScore[i]) {
            maxScore = matchScore[i];
            answer = i;
        }
    }
    
    return answer;
}

int getLinkNum(int idx, string page, int N){ // 링크 수 및 연결된 링크구하기
    string linkTag = "<a href="; 
    string httpTag = "https://";
    string linkedPage = "";
    int res = 0;
    while(1) {
        int n = page.find(linkTag);
        if(n == -1) return res; // 더이상 링크가 없다면 리턴
        page = page.substr(n);
        n = page.find(httpTag);
        page = page.substr(n);
        n = page.find('"');
        linkedPage = page.substr(0, n); // 링크된 페이지
        for(int i=0; i<N; i++){
            if(pageName[i] == linkedPage) {
                link[i].push_back(idx);
            }
        }
        page = page.substr(n+1);
        res++;
    }
    return res;
}

int getBasicScore(string word, string page){ // 기본점수
    for(auto &c : word) c = toupper(c);
    for(auto &c : page) c = toupper(c);
    int res = 0;
    while(1) {
        int n = page.find(word);
        if(n == -1) break;
        if(!isAlpha(page[n-1]) && !isAlpha(page[n+word.size()])) res++;
        page = page.substr(n+1);
    }
    return res;
}

string getPageName(string page){ // 페이지 이름
    string contentTag = "<meta property=\"og:url\" content=";
    string httpTag = "https://";
    
    int n = page.find(contentTag);
    page = page.substr(n);
    n = page.find(httpTag);
    page = page.substr(n);
    n = page.find('"');
    page = page.substr(0, n);
    return page;
}

bool isAlpha(char A) { //알파벳인가
    return (A >= 'A' && A <= 'Z');
}
저작자표시

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

[C++][프로그래머스] 파일명 정렬  (0) 2020.08.28
[C++][프로그래머스] 오픈채팅방  (0) 2020.08.28
[C++][프로그래머스] 징검다리 건너기  (0) 2020.08.13
[C++][프로그래머스] 짝지어 제거하기  (0) 2020.08.13
[C++][프로그래머스] 압축  (0) 2020.08.13
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday