문제
- 문제 링크
- 문제 설명: 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
- 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
- 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
- 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
- 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
- 검색어 word와 웹페이지의 HTML 목록인 pages가 주어졌을 때, 매칭점수가 가장 높은 웹페이지의 index를 구하라. 만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 반환하는 함수를 작성
- 입력
- pages는 길이는 1 이상 20 이하
- 한 웹페이지 문자열의 길이는 1 이상 1,500 이하
- 한 웹페이지의 url은 HTML의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.
- <meta property="og:url" content="https://careers.kakao.com/index" />
- 한 웹페이지에서 모든 외부 링크는 <a href="https://URL"></a>
- <a> 내에 다른 attribute가 주어지는 경우는 없으며 항상 href로 연결할 사이트의 url만 포함된다.
- word의 길이는 1 이상 12 이하
- 검색어를 찾을 때, 대소문자 구분은 무시하고 찾는다.
- 검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영한다.
- 단어는 알파벳을 제외한 다른 모든 문자로 구분한다.
- 출력: 매칭 점수가 가장 높은 웹페이지의 인덱스
풀이
- 먼저 각 웹 페이지마다 외부 링크를 찾아내서 모두 저장하는데 이 과정에서 페이지의 텍스트를 검사해서 기본 점수와 URL을 찾아낸다.
- map<string, int> 자료형으로 URL 별 페이지 인덱스를 별도로 저장한다.
- 페이지의 외부 링크를 돌면서 URL이 현재 pages 배열에 있는 페이지의 것이면 (기본 점수 / 외부 링크 수) 를 계산해서 외부 링크 페이지의 점수에 더해준다.
- 점수 내림차순, 인덱스 오름차순으로 정렬 후 첫번째 원소의 인덱스를 반환
- meta 태그로 페이지 URL을 탐색할 때 property와 같은 모든 속성에 대해서도 키워드를 주고 찾아야 함
- <meta content="~"> 와 같은 것은 안됌
- 검색어 탐색에서 대소문자를 무시하므로 맨 처음에 페이지의 모든 텍스트를 소문자로 변경하는 것이 이후 텍스트 처리하기 편함
- transform(html.begin(), html.end(), ::tolower)
- 외부 링크를 찾고나서 웹페이지 텍스트를 찾을 때는 body 안에서만 해도 유효하며, 알파벳 외에 모든 문자를 공백으로 치환하는 것이 좋음
- replace_if(body.begin(), body.end(), 알파벳 아니면 true/맞으면 false 함수, 공백)
- 정답 코드
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <sstream>
using namespace std;
const string urlPrefix = "https://";
int solution(string word, vector<string> pages) {
map<string, int> m; // (url, page index)
vector<string> links[pages.size()];
vector<int> numWords(pages.size(), 0);
vector<pair<double, int>> totalScore;
// 검색 단어 소문자로 치환
transform(word.begin(), word.end(), word.begin(), ::tolower);
for (int i = 0; i < pages.size(); i++) {
// 페이지 텍스트 모두 소문자로 치환
string& html = pages[i];
transform(html.begin(), html.end(), pages[i].begin(), ::tolower);
// 페이지 URL 탐색
string token = "<meta property=\"og:url\" content=\"" + urlPrefix;
int tokenStart = html.find(token);
int tokenEnd = html.find("\"", tokenStart + token.size());
int urlStart = tokenStart + token.size() - urlPrefix.size();
m[html.substr(urlStart, tokenEnd - urlStart)] = i;
// body 텍스트 분리
int bodyStart = html.find("<body>") + 6;
int bodyEnd = html.find("</body>") - 1;
string body = html.substr(bodyStart, bodyEnd - bodyStart);
// 외부 링크 탐색
token = "<a href=\"" + urlPrefix;
tokenStart = body.find(token);
while (tokenStart != string::npos) {
tokenEnd = body.find("\"", tokenStart + token.size());
urlStart = tokenStart + token.size() - urlPrefix.size();
links[i].push_back(body.substr(urlStart, tokenEnd - urlStart));
tokenStart = body.find(token, urlStart + links[i].back().size());
}
// 알파벳 외에 모두 공백으로 치환 후 단어 탐색
replace_if(body.begin(), body.end(), [](auto& ch) { return !isalpha(ch); }, ' ');
istringstream iss(body);
while (getline(iss, token, ' '))
if (token == word) numWords[i]++;
totalScore.push_back({numWords[i], i});
}
// 외부 링크마다 pages에 존재하는 페이지면 링크 점수를 계산해서 더해줌
for (int i = 0; i < pages.size(); i++) {
int linkSize = links[i].size();
for (string& l : links[i])
if (m.find(l) != m.end())
totalScore[m[l]].first += (double)numWords[i] / (double)linkSize;
}
// 매칭 점수 내림차순, 인덱스 오름차순으로 정렬
sort(totalScore.begin(), totalScore.end(), [&](auto& a, auto& b) mutable {
if (a.first == b.first) return a.second < b.second;
return a.first > b.first;
});
return totalScore[0].second;
}
