코딩테스트 -- 매칭 점수 - (프로그래머스 / C++)

728x90

문제!

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

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

예를 들어, 다음과 같이 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> 내에 다른 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을 리턴하면 된다.

문제가 좀 길긴한데

<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://a.com"/>
</head>
<body>
Blind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. 
<a href="https://b.com"> Link to b </a>
</body>
</html>

위 처럼 주어진 html의 정보를 구하는?

구해야 할 껀 많지만, 따로 풀이 방법이 있는게 아니라 그냥 풀어나가면 되는 문제였습니다!

일단 구해야할게

1. 기본점수

2. 외부링크 수

3. 외부링크 수에 따른 링크점수

기본점수 + 링크점수 = 매칭점수

매칭 점수가 가장 높은 링크 인덱스를 출력하면 끝!

이제 코드 시작!

이란 사용될것 같은 변수들을 선언해주고 시작합시다!

int link[20];//링크
string link_name[20];//링크이름
int score[20];//기본점수

double count_link[20];//외부링크수
vector <int> link_list[20];// 각 링크의 외부 링크 리스트

double link_score[20];//링크점수 = 기본점수 / 외부 링크수
double matchScore[20]; // 전체점수

가장 먼저 주소의 이름과 기본점수를 계산해줍시다.

int solution(string word, vector<string> pages) {
    int answer = 0;
    
    
    //저장해야할거 1. 주소 2. 외부링크 3.body 내용
    string memo;
    
    
    for(int i=0;i<pages.size();i++){
        link_save(pages[i],i);
        score_cal(word,pages[i],i);
    }

링크 이름을 찾는 방법은 아래와 같습니다!

void link_save(string page, int i){
    string Point1 = "<meta property=\"og:url\" content=";
    string Point2 = "https://";
    
    int n = page.find(Point1);
    page = page.substr(n);
    
    n = page.find(Point2);
    page = page.substr(n);
    
    n = page.find('"');
    page = page.substr(0, n);
    link_name[i]=page;
    
}

주소를 제외한 나머지 부분을 제외하는 방법!

그리고 기본 점수 계산 하는 방법도 위와 비슷한 방법을 통한 탐색으로 해결 가능!

bool isAlpha(char A) { //알파벳인지
    return (A >= 'A' && A <= 'Z');
}

void score_cal(string word, string page,int i){
    for(auto &c : word){// 대문자 처리
        c = toupper(c);
    } 
    
    for(auto &c : page){
        c = toupper(c);
    } 
    
    double 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);// 탐색끝날때마다 잘라주기!
    }
    score[i]=res;
}

다음은 연결된 링크들을 찾아줍시다.

for(int i=0;i<pages.size();i++){
        count_link[i]=link_count(pages[i],i,pages.size());
    }

탐색 방법은 위의 방법들과 동일하고 링크된 위치에 저장!

int link_count(string page, int index, int page_size){//외부링크 세기
    string Point1 = "<a href="; 
    string Point2 = "https://";
    string memo = "";
    double res = 0;
    
    while(1) {// 탐색!
        int n = page.find(Point1);
        if(n == -1){
            return res; // 더이상 링크가 없다면 리턴
        } 
        
        page = page.substr(n);// 링크 찾을때와 같은방식
        n = page.find(Point2);
        page = page.substr(n);
        n = page.find('"');
        
        memo = page.substr(0, n); // 링크된 페이지 저장
        
        
        
        for(int i=0; i<page_size; i++){// 링크 찾아서 인덱스 추가
            if(link_name[i] == memo) {
                link_list[i].push_back(index);// 현재 링크 리스트에 추가
            }
        }
        page = page.substr(n+1);
        res++;
    }
    
    return res;
    
}

다음은 매칭 점수를 구하는 부분으로 아래에선 링크점수와 기본점수를 동시에 구하고 불러와 계산하는 방식!

 double max_S = 0.0;
    for(int i=0; i<pages.size(); i++){ // 매칭점수 구하기
        matchScore[i] = (double)score[i];
        for(int j=0; j<link_list[i].size(); j++){
            matchScore[i] += ((double)score[link_list[i][j]] / count_link[link_list[i][j]]);
        }
        if(max_S < matchScore[i]) {
            max_S = matchScore[i];
            answer = i;
        }
    }

이렇게 안하고 나눠서 했더니 왜 오류나는지 모르겠는데 안되네요...

하기전에... 열심히 했는데 실패한 코드...

    double max_S = 0.0;
    
    for(int i=0; i<pages.size(); i++){ // 링크점수 구하기
        link_score[i] = ((double)score[i] / count_link[i]);
        
    }
    
     
    for(int i=0; i<pages.size(); i++){ // 매칭점수 구하기
        for(int j=0; j<link_list[i].size(); j++){
            score[i]+=link_score[link_list[i][j]];
        }
    }
    
    
    
    for(int i=0; i<pages.size(); i++){//최댓값 구하기
        if(max_S<score[i]){
            max_S=score[i];
            answer=i;
        }
    }

테스트 케이스 4, 10 ,14 만 틀리네요.... 이유가 머지;;

이건 나중에 생각해보겠습니다.

일단 여기까지가 끝!

단순 탐색과 연산만 잘하면 충분히 해결가능한 문제였습니다!

#include <string>
#include <vector>

#include <iostream>
using namespace std;

int link[20];//링크
string link_name[20];//링크이름
int score[20];//기본점수

double count_link[20];//외부링크수
vector <int> link_list[20];// 각 링크의 외부 링크 리스트

double link_score[20];//링크점수 = 기본점수 / 외부 링크수
double matchScore[20]; // 전체점수


bool isAlpha(char A) { //알파벳인지
    return (A >= 'A' && A <= 'Z');
}

void link_save(string page, int i){
    string Point1 = "<meta property=\"og:url\" content=";
    string Point2 = "https://";
    
    int n = page.find(Point1);
    page = page.substr(n);
    
    n = page.find(Point2);
    page = page.substr(n);
    
    n = page.find('"');
    page = page.substr(0, n);
    link_name[i]=page;
    
}

void score_cal(string word, string page,int i){
    for(auto &c : word){// 대문자 처리
        c = toupper(c);
    } 
    
    for(auto &c : page){
        c = toupper(c);
    } 
    
    double 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);// 탐색끝날때마다 잘라주기!
    }
    score[i]=res;
}


int link_count(string page, int index, int page_size){//외부링크 세기
    string Point1 = "<a href="; 
    string Point2 = "https://";
    string memo = "";
    double res = 0;
    
    while(1) {// 탐색!
        int n = page.find(Point1);
        if(n == -1){
            return res; // 더이상 링크가 없다면 리턴
        } 
        
        page = page.substr(n);// 링크 찾을때와 같은방식
        n = page.find(Point2);
        page = page.substr(n);
        n = page.find('"');
        
        memo = page.substr(0, n); // 링크된 페이지 저장
        
        
        
        for(int i=0; i<page_size; i++){// 링크 찾아서 인덱스 추가
            if(link_name[i] == memo) {
                link_list[i].push_back(index);// 현재 링크 리스트에 추가
            }
        }
        page = page.substr(n+1);
        res++;
    }
    
    return res;
}

int solution(string word, vector<string> pages) {
    int answer = 0;
    //저장해야할거 1. 주소 2. 외부링크 3.body 내용
    string memo;
    
    for(int i=0;i<pages.size();i++){
        link_save(pages[i],i);
        score_cal(word,pages[i],i);
    }
    
    for(int i=0;i<pages.size();i++){
        count_link[i]=link_count(pages[i],i,pages.size());
    }
    
    double max_S = 0.0;
    for(int i=0; i<pages.size(); i++){ // 매칭점수 구하기
        matchScore[i] = (double)score[i];
        for(int j=0; j<link_list[i].size(); j++){
            matchScore[i] += ((double)score[link_list[i][j]] / count_link[link_list[i][j]]);
        }
        if(max_S < matchScore[i]) {
            max_S = matchScore[i];
            answer = i;
        }
    }
 
    return answer;
}

좀 많이 기네요;;

틀린점이 있다면 댓 달아주세요!

'코딩테스트!(프로그래머스 & 백준) > 프로그래머스-C++' 카테고리의 다른 글

코딩테스트 -- 징검다리 - (프로그래머스 / C++) (1)	2022.09.02
코딩테스트 -- 카드 짝 맞추기 - (프로그래머스 / C++) (0)	2022.08.31
코딩테스트 -- 스타 수열 - (프로그래머스 / C++) (1)	2022.08.29
코딩테스트 -- 사라지는 발판 - (프로그래머스 / C++) (0)	2022.08.27
코딩테스트 -- 선입 선출 스케줄링 - (프로그래머스 / C++) (0)	2022.08.22

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

오늘도 열시미!

코딩테스트 -- 매칭 점수 - (프로그래머스 / C++)

'코딩테스트!(프로그래머스 & 백준) > 프로그래머스-C++' 카테고리의 다른 글

댓글

티스토리툴바

코딩테스트 -- 매칭 점수 - (프로그래머스 / C++)

'코딩테스트!(프로그래머스 & 백준) > 프로그래머스-C++' 카테고리의 다른 글

관련글

댓글

티스토리툴바