프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다. 그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
예를 들어, 다음과 같이 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이하이다.
검색어 word는 하나의 영어 단어로만 주어지며 알파벳 소문자와 대문자로만 이루어져 있다.
word의 길이는1이상12이하이다.
검색어를 찾을 때, 대소문자 구분은 무시하고 찾는다.
예를들어 검색어가 blind일 때, HTML 내에 Blind라는 단어가 있거나, BLIND라는 단어가 있으면 두 경우 모두 해당된다.
검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영한다.
단어는 알파벳을 제외한 다른 모든 문자로 구분한다.
예를들어 검색어가 "aba" 일 때, "abab abababa"는 단어 단위로 일치하는게 없으니, 기본 점수는 0점이 된다.
만약 검색어가 "aba" 라면, "aba@aba aba"는 단어 단위로 세개가 일치하므로, 기본 점수는 3점이다.
결과를 돌려줄때, 동일한 매칭점수를 가진 웹페이지가 여러 개라면 그중 index 번호가 가장 작은 것를 리턴한다
즉, 웹페이지가 세개이고, 각각 매칭점수가 3,1,3 이라면 제일 적은 index 번호인 0을 리턴하면 된다.
풀이
문제의 길이와 요구하는 조건이 많아서 까다로웠지, 문제에서 하라는 대로 구현하면 되는 문제였다.
물론 그것이 굉장히 길고 오래걸려 짜증나는 것이 문제였다.
코드
함수() 모를만한 함수 있다면 정리하기
1. 페이지 구조체 선언
struct Page {
int idx; // 페이지 번호
vector<string> out_url_list; // 외부 url 리스트
int basic_point; // 기본 점수
double link_point; // 링크 점수
double match_point; // 매칭 점수
};
vector<Page> page_list;
string WORD;
map<string, int> page_num;
2. 소문자로 변환하기
string tolower(string word) {
for (int i = 0; i < word.length(); i++) {
word[i] = tolower(word[i]);
}
return word;
}
3. URL 가져오기
string get_url(string page) {
string front_url = "<meta property=\"og:url\" content=\"https://";
string url = "";
int idx = page.find(front_url); // front_url의 시작 문자인 <의 위치를 반환한다.
idx += front_url.length(); // 그러므로 front_url의 길이만큼 더해준다.
while (page[idx] != '\"') {
url += page[idx];
idx++;
}
return url;
}
4. 외부링크 가져오기
vector<string> get_out_url(string page) {
vector<string> url_list;
string front_url = "<a href=\"https://";
int idx = page.find(front_url);
while (idx != page.npos) {
idx += front_url.length();
string url = "";
while (page[idx] != '\"') {
url += page[idx];
idx++;
}
url_list.push_back(url);
page = page.substr(idx); // 남은 부분을 가져와서
idx = page.find(front_url); // 다시 반복문 시작
}
return url_list;
}
5. 페이지 별로 텍스트를 찾아 기본점수 구하기
int find_text(string page) {
string start = "<body>";
string end = "</body>";
int s = page.find(start);
s += start.length();
int e = page.find(end);
page = page.substr(s, e - s);
string text = "";
int count = 0;
for (int i = 0; i < page.length(); i++) {
if (!isalpha(page[i])) {
if (text == WORD) {
count++;
}
text = "";
}
else {
text += page[i];
}
}
return count;
}
6. 구조체에 저장하기
void save_page(vector<string> pages) {
int num = 0;
for (string page : pages) {
string page_to_low = tolower(page);
string url = get_url(page_to_low);
page_num[url] = num + 1;
vector<string> out_url_list = get_out_url(page_to_low);
int basic_point = find_text(page_to_low);
page_list.push_back({ num, out_url_list, basic_point, 0.0, 0.0 });
num++;
}
}
7. 링크점수를 구한 후 매칭점수 구하기
int cal_point() {
int p_size = page_list.size();
double max_match_point = -999999999.0;
int index = -1;
for (int i = 0; i < p_size; i++) {
vector<string> out_pages = page_list[i].out_url_list;
int o_size = out_pages.size();
for (int j = 0; j < o_size; j++) {
string url = out_pages[j];
if (page_num[url] != 0) {
int idx = page_num[url] - 1;
page_list[idx].link_point += ((double)page_list[i].basic_point / (double)o_size);
}
}
}
for (int i = 0; i < p_size; i++) {
page_list[i].match_point = (double)page_list[i].basic_point + page_list[i].link_point;
if (page_list[i].match_point > max_match_point) {
max_match_point = page_list[i].match_point;
index = page_list[i].idx;
}
}
return index;
}
전체 코드
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
struct Page {
int idx; // 페이지 번호
vector<string> out_url_list; // 외부 url 리스트
int basic_point; // 기본 점수
double link_point; // 링크 점수
double match_point; // 매칭 점수
};
vector<Page> page_list;
string WORD;
map<string, int> page_num;
string tolower(string word) {
for (int i = 0; i < word.length(); i++) {
word[i] = tolower(word[i]);
}
return word;
}
string get_url(string page) {
string front_url = "<meta property=\"og:url\" content=\"https://";
string url = "";
int idx = page.find(front_url); // front_url의 시작 문자인 <의 위치를 반환한다.
idx += front_url.length(); // 그러므로 front_url의 길이만큼 더해준다.
while (page[idx] != '\"') {
url += page[idx];
idx++;
}
return url;
}
vector<string> get_out_url(string page) {
vector<string> url_list;
string front_url = "<a href=\"https://";
int idx = page.find(front_url);
while (idx != page.npos) {
idx += front_url.length();
string url = "";
while (page[idx] != '\"') {
url += page[idx];
idx++;
}
url_list.push_back(url);
page = page.substr(idx); // 남은 부분을 가져와서
idx = page.find(front_url); // 다시 반복문 시작
}
return url_list;
}
int find_text(string page) {
string start = "<body>";
string end = "</body>";
int s = page.find(start);
s += start.length();
int e = page.find(end);
page = page.substr(s, e - s);
string text = "";
int count = 0;
for (int i = 0; i < page.length(); i++) {
if (!isalpha(page[i])) {
if (text == WORD) {
count++;
}
text = "";
}
else {
text += page[i];
}
}
return count;
}
void save_page(vector<string> pages) {
int num = 0;
for (string page : pages) {
string page_to_low = tolower(page);
string url = get_url(page_to_low);
page_num[url] = num + 1;
vector<string> out_url_list = get_out_url(page_to_low);
int basic_point = find_text(page_to_low);
page_list.push_back({ num, out_url_list, basic_point, 0.0, 0.0 });
num++;
}
}
int cal_point() {
int p_size = page_list.size();
double max_match_point = -999999999.0;
int index = -1;
for (int i = 0; i < p_size; i++) {
vector<string> out_pages = page_list[i].out_url_list;
int o_size = out_pages.size();
for (int j = 0; j < o_size; j++) {
string url = out_pages[j];
if (page_num[url] != 0) {
int idx = page_num[url] - 1;
page_list[idx].link_point += ((double)page_list[i].basic_point / (double)o_size);
}
}
}
for (int i = 0; i < p_size; i++) {
page_list[i].match_point = (double)page_list[i].basic_point + page_list[i].link_point;
if (page_list[i].match_point > max_match_point) {
max_match_point = page_list[i].match_point;
index = page_list[i].idx;
}
}
return index;
}
int solution(string word, vector<string> pages) {
int answer = 0;
WORD = tolower(word);
save_page(pages);
answer = cal_point();
return answer;
}
