티스토리 뷰
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의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.
- 예를 들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은 https://careers.kakao.com/index 이다.
- <meta property="og:url" content="https://careers.kakao.com/index" />
- 한 웹페이지에서 모든 외부 링크는 <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을 리턴하면 된다.
입출력 예
| word | pages | return |
| "blind" | <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> |
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://b.com\"/> </head> <body> Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum, <a href=\"https://a.com\"> Link to a </a> blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut. <a href=\"https://c.com\"> Link to c </a> </body> </html> |
||
| <html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\"> <head> <meta charset=\"utf-8\"> <meta property=\"og:url\" content=\"https://c.com\"/> </head> <body> Ut condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind <a href=\"https://a.com\"> Link to a </a> </body> </html> |
||
| "Muzi" | <html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\"> <head> <meta charset=\"utf-8\"> <meta property=\"og:url\" content=\"https://careers.kakao.com/interview/list\"/> </head> <body> <a href=\"https://programmers.co.kr/learn/courses/4673\"></a>#!MuziMuzi!)jayg07con&& </body> </html> |
1 |
| <html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\"> <head> <meta charset=\"utf-8\"> <meta property=\"og:url\" content=\"https://www.kakaocorp.com\"/> </head> <body> con% muzI92apeach&2<a href=\"https://hashcode.co.kr/tos\"></a> ^ </body> </html> |
코드
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
struct page
{
string url; // 현재 페이지의 url
vector<int> link; // 현재 페이지로 링크가 걸린 다른 페이지의 인덱스
int link_num; // 현재 페이지에서 다른 페이지로 링크가 걸린 개수
int basic_score; // 현재 페이지의 기본 점수
double match_score; // 현재 페이지의 매칭 점수 (기본 점수 + 링크 점수)
void init()
{
url.clear();
link.clear();
link_num = 0;
basic_score = 0;
match_score = 0;
}
};
unordered_map<string, int> url_list; // key: 페이지의 url, value: 페이지의 인덱스
vector<page> web_page; // 각 페이지의 정보
// 문자열과 문자열에서 url이 시작하는 인덱스가 주어지면
// url을 뽑아서 리턴함
string get_url(string &s, int idx)
{
string res = "";
while (s[idx] != '\"')
res += s[idx++];
return res;
}
// <body> </body> 사이의 내용을 읽어서
// 현재 페이지의 기본 점수를 구하고 외부 링크를 찾음
void get_body(string &s, string &word, int index)
{
int idx = s.find("<body>") + 7;
int end = s.find("</body>");
int link_idx;
string tmp;
string href = "<a href=\"https://";
// <body> </body> 사이의 내용을 읽음
while (idx < end)
{
tmp.clear();
// 알파벳으로 이루어진 단어를 뽑음
while (isalpha(s[idx]))
{
tmp += s[idx++];
}
// 뽑은 단어가 없으면 다시 찾음
if (tmp.empty())
{
idx++;
continue;
}
// 뽑은 단어가 검색어(word)와 일치하는 경우
if (tmp.compare(word) == 0)
{
web_page[index].basic_score++;
}
// 유효한 외부 링크인 경우
if (tmp.compare("a") == 0 && s.substr(idx - 2).find(href) == 0)
{
link_idx = url_list[get_url(s, idx + 15)] - 1;
if (link_idx >= 0)
web_page[link_idx].link.push_back(index);
web_page[index].link_num++;
}
}
}
int solution(string word, vector<string> pages) {
int answer = 0;
page p;
int i, j, idx;
double max_score = 0;
string meta = "<meta property=\"og:url\" content=\"https://";
// 검색어를 소문자로 변환
transform(word.begin(), word.end(), word.begin(), ::tolower);
// 페이지를 소문자로 변환 후 url을 추출함
for (i = 0; i < pages.size(); i++)
{
transform(pages[i].begin(), pages[i].end(), pages[i].begin(), ::tolower);
p.init();
p.url = get_url(pages[i], pages[i].find(meta) + 41);
web_page.push_back(p);
url_list[p.url] = i + 1;
}
// 페이지의 <body> 태그를 읽음
for (i = 0; i < pages.size(); i++)
{
get_body(pages[i], word, i);
}
// 페이지의 매칭 점수를 계산함
for (i = 0; i < web_page.size(); i++)
{
// 기본 점수로 초기화
web_page[i].match_score = web_page[i].basic_score;
// 모든 링크에 대하여 링크 점수를 더함
for (j = 0; j < web_page[i].link.size(); j++)
{
idx = web_page[i].link[j];
web_page[i].match_score += (double)web_page[idx].basic_score / web_page[idx].link_num;
}
// 매칭 점수의 최댓값과 인덱스를 갱신
if (max_score < web_page[i].match_score)
{
max_score = web_page[i].match_score;
answer = i;
}
}
return answer;
}
페이지의 <body> 부분을 읽기 전에 모든 페이지의 url과 인덱스를 해시맵 url_list에 저장했다. 이렇게 한 이유는 외부 링크로 연결된 페이지의 정보에 쉽게 접근하기 위함이다. 이때, pages로 주어지지 않은 페이지에 대한 외부 링크를 처리하기 위해 (인덱스 + 1)을 저장한다. pages로 주어지지 않은 페이지에 대한 value는 0인데, 0번 인덱스부터 저장하면 이 둘을 구분할 수 없다.
모든 페이지의 url과 인덱스를 저장하여 url_list를 완성했다면 각 페이지의 <body> 부분을 읽는다. 이 과정에서 검색어 word와 일치하는 단어의 수를 세어 기본 점수를 계산하고, 외부 링크를 찾아 저장한다. 외부 링크는 <a> 태그로 표현되므로 "a"라는 단어를 찾은 경우 이 단어가 외부 링크를 나타내는 태그인지 확인한다. 외부 링크라면 해당하는 페이지의 인덱스를 찾는다. 이때 1을 더해서 저장했기 때문에 1을 빼서 가져오는데, 만약 pages로 주어지지 않은 페이지에 대한 외부 링크인 경우에는 인덱스가 -1이 된다. 벡터 web_page에 저장된 페이지인 경우 현재 페이지의 인덱스를 저장해주고, 현재 페이지의 외부 링크 수도 1만큼 증가시킨다.
이제 필요한 정보들이 모두 web_page에 저장되었다. 각 페이지에 대해 매칭 점수를 계산하여 최댓값을 가지는 페이지의 인덱스를 찾으면 된다.
처음 제출했을 때, 테스트 9만 틀렸었다. 원인은 검색하는 문자열이었다. "content="와 같이 부분적인 문자열이 아니라 다음과 같이 태그까지 포함하여 검색해야 올바른 결과를 얻을 수 있다.
string meta = "<meta property=\"og:url\" content=\"https://";
string href = "<a href=\"https://";
링크
코딩테스트 연습 - 매칭 점수
매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀
programmers.co.kr
inbdni/Programmers
Contribute to inbdni/Programmers development by creating an account on GitHub.
github.com
728x90
'Coding Test > Programmers' 카테고리의 다른 글
| [프로그래머스] 음양 더하기 / C++ (0) | 2021.04.29 |
|---|---|
| [프로그래머스] 괄호 회전하기 / C++ (0) | 2021.04.23 |
| [프로그래머스] 셔틀버스 / C++ (0) | 2021.03.10 |
| [프로그래머스] 길 찾기 게임 / C++ (0) | 2021.03.10 |
| [프로그래머스] 스티커 모으기(2) / C++ (0) | 2021.03.08 |