문제 설명
매칭 점수
프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
- 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
- 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
- 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
- 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
예를 들어, 다음과 같이 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을 리턴하면 된다.
접근 방법
문제를 해결하기 위해 크게 5가지 방법으로 나눌 수 있습니다.
1. 대문자를 모두 소문자로 전처리하기
2. 자신의 페이지 이름 파악하기
3. 페이지의 기본 점수 구하기
4. 자신의 페이지를 A, 외부로 나가는 링크를 B라 한다면 A에서 외부로 나가는 링크 B를 저장하고, B는 자신으로 들어오는 링크 A를 저장하기
5. 점수 구하기
일단 위의 과정을 설명하기 이전에 문제를 해결하기 위해 전역변수로 사용한 4개의 HashMap에 대해 설명하겠습니다.
1. map<int, string> name; => name[페이지index] = "페이지 주소"
2. map<string, int> score; => score[페이지 주소] = 기본 점수
3. map<string, vector<string>> outdegree; => outdegree["페이지 주소"] = {외부로 나가는 링크들}
4. map<string, vector<string>> indegree; => indegree["페이지 주소"] = {자신으로 들어오는 외부 링크들}
1. 대문자를 모두 소문자로 전처리하기
아스키 코드 표를 사용하여 어렵지 않게 소문자로 변환할 수 있습니다.
void toSmall(string &page){
for(int j=0;j<page.size();j++)
if(65 <= int(page[j]) && int(page[j]) <= 90)
page[j] = char(int(page[j]) + 32);
}
2. 자신의 페이지 이름 파악하기
string 헤더의 find함수를 적절히 사용하여 구할 수 있었습니다. 자신의 페이지 주소 뿐만 아니라 용도에 맞게 어떠한 페이지의 주소라도 파악할 수 있도록 pattern이라는 매개변수를 추가하였습니다.
만약 자신의 페이지 주소를 파악하기 위해서는 pattern = "<meta property=\"og:url\" content="가 될 것이며
외부로 링크의 페이지 주소를 파악하기 위해서는 pattern = "<a href=" 가 될 것입니다.
(참고로 문자열 안에 "를 사용하려면 \를 붙여 사용할 수 있습니다.)
//string myNamePattern = "<meta property=\"og:url\" content=";
// string outLinkPattern = "<a href=";
string getLinks(string &page, string pattern, int &idx){
string url = "";
idx = page.find(pattern, idx);
if(idx == string::npos) return url;
else idx += pattern.size();
while(page[++idx] != '"')
url += page[idx];
return url;
}
이 함수는 찾아낸 페이지의 주소의 문자열을 반환하며, idx를 참조로 받아 동시에 페이지 주소가 끝나는 지점의 index로 갱신됩니다.
3. 기본점수 구하기
기본점수는 페이지 문서 내에서 해당 단어가 몇번 등장하는지 찾을 수 있습니다. 단어의 앞뒤에 영어 철자가 존재하면 안된다는 규칙이 있어 단어를 찾아낸 뒤에 단어의 시작 지점보다 한 칸 앞과 단어의 끝 지점의 한 칸 뒤를 모두 확인해야 합니다. 이 때 cnt는 페이지에서 찾은 word의 수 입니다.
int getScore(string &word, string &page){
int idx = page.find(word);
int cnt = 0;
while(page.find(word, idx) != string::npos){ //단어를 찾을 수 있는 동안에
bool isWord = true;
idx = page.find(word, idx);
//단어의 앞 부분 확인
if(0 <= idx - 1 && idx - 1 < page.size() && 'a' <= page[idx - 1] && page[idx - 1] <= 'z')
isWord = false;
//단어의 뒷 부분 확인
if(0 <= idx + word.size() && idx + word.size() < page.size() && 'a' <= page[idx + word.size()] && page[idx + word.size()] <= 'z')
isWord = false;
if(isWord)
cnt++;
idx += word.size();
}
return cnt;
}
4. 자신의 페이지를 A, 외부로 나가는 링크를 B라 한다면 A에서 외부로 나가는 링크 B를 저장하고, B는 자신으로 들어오는 링크 A를 저장하기
2번에서 설명한 getLinks 함수를 사용하여 while문으로 문서의 끝까지 외부로 나가는 링크가 있는지 탐색을 하여 hashmap인 indegree와 outdegree에 등록합니다.
pos = 0;
while(pos != string::npos){
string link = getLinks(page, outLinkPattern, pos);
if(link.size() == 0)
break;
outdegree[myName].push_back(link);
indegree[link].push_back(myName);
}
5. 점수 구하기
이제 점수를 구하기 위한 모든 정보를 저장했습니다. 매칭 점수는 아래의 수식으로 구할 수 있습니다.
매칭 점수 = 자신의 기본점수 + (외부로 나가는 링크들의 '링크 점수')
링크 점수 = (링크의 기본점수/링크의 외부로 나가는 링크)
(참고로 여기서 자료형을 float을 사용하면 통과하지 못하는 테스트 케이스가 있었습니다.)
double getMatchScore(int idx){
string myName = name[idx];
double baseScore = double(score[myName]);
double linkScore = 0;
vector<string> inLinks = indegree[myName];
for(int i=0;i<inLinks.size();i++){
string link = inLinks[i];
linkScore += (double(score[link]) / double(outdegree[link].size()));
}
return baseScore + linkScore;
}
소스 코드
#include <string>
#include <vector>
#include <map>
using namespace std;
map<int, string> name;
map<string, int> score;
map<string, vector<string>> outdegree;
map<string, vector<string>> indegree;
void toSmall(string &page){
for(int j=0;j<page.size();j++)
if(65 <= int(page[j]) && int(page[j]) <= 90)
page[j] = char(int(page[j]) + 32);
}
string getLinks(string &page, string pattern, int &idx){
string url = "";
idx = page.find(pattern, idx);
if(idx == string::npos) return url;
else idx += pattern.size();
while(page[++idx] != '"')
url += page[idx];
return url;
}
int getScore(string &word, string &page){
int idx = page.find(word);
int cnt = 0;
while(page.find(word, idx) != string::npos){
bool isWord = true;
idx = page.find(word, idx);
if(0 <= idx - 1 && idx - 1 < page.size() && 'a' <= page[idx - 1] && page[idx - 1] <= 'z')
isWord = false;
if(0 <= idx + word.size() && idx + word.size() < page.size() && 'a' <= page[idx + word.size()] && page[idx + word.size()] <= 'z')
isWord = false;
if(isWord)
cnt++;
idx += word.size();
}
return cnt;
}
void processing(string &word, string &page, int idx){
string myNamePattern = "<meta property=\"og:url\" content=";
string outLinkPattern = "<a href=";
int pos = 0;
string myName = getLinks(page, myNamePattern, pos); //함수 내부에 참조연산자를 사용하여 pos가 변할 수 있음
name.insert({idx, myName});
int cnt = getScore(word, page);
score.insert({myName, cnt});
pos = 0;
while(pos != string::npos){
string link = getLinks(page, outLinkPattern, pos);
if(link.size() == 0)
break;
outdegree[myName].push_back(link);
indegree[link].push_back(myName);
}
}
double getMatchScore(int idx){
string myName = name[idx];
double baseScore = double(score[myName]);
double linkScore = 0;
vector<string> inLinks = indegree[myName];
for(int i=0;i<inLinks.size();i++){
string link = inLinks[i];
linkScore += (double(score[link]) / double(outdegree[link].size()));
}
return baseScore + linkScore;
}
int solution(string word, vector<string> pages) {
int answer = 0;
toSmall(word);
for(int i=0;i<pages.size();i++)
toSmall(pages[i]);
for(int i=0;i<pages.size();i++)
processing(word, pages[i], i);
double maxScore = 0;
for(int i=0;i<pages.size();i++){
double nowScore = getMatchScore(i);
if(maxScore < nowScore){
maxScore = nowScore;
answer = i;
}
}
return answer;
}'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [C++] Summer/winter coding(2019) 지형 이동 (0) | 2021.03.16 |
|---|---|
| [C++] 2019 카카오 블라인드 블록 게임 (0) | 2021.02.16 |
| [C++] 2019 카카오 블라인드 길 찾기 게임 (0) | 2021.02.16 |
| [C++] 2020 카카오 블라인드 블록이동하기 (0) | 2021.02.14 |
| [C++] 2020 카카오 블라인드 외벽 점검 (0) | 2021.02.10 |