프로그래머스/카카오
[프로그래머스/Level 3/C++/2019 카카오 블라인드 채용] 매칭점수
Vfly
2023. 1. 30. 21:42
https://school.programmers.co.kr/learn/courses/30/lessons/42893
- 출처 : 프로그래머스 코딩 테스트 연습
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[문제 요약]
- 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
- 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
- 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
- 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
- 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
- 예를 들어, 다음과 같이 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을 리턴하면 된다.
[문제 풀이]
문제 자체를 이해하는데 어렵지는 않지만 구현하는데 꽤 귀찮은 부분이 많은 문제였다.
먼저, 구해야하는 것들을 정리해보자.
- 한 웹페이지에서 word가 나오는 횟수를 구해야한다. ( 기본 점수 ) ( scores[i][0] )
- 한 웹페이지에서 외부 링크의 개수를 구해야한다. ( 외부 링크의 개수 ) ( scores[i][1] )
- 한 웹페이지로 링크가 걸린 다른 웹페이지의 (기본점수 / 외부 링크의 개수)의 총합을 구한다 ( scores[i][2] )
- 매칭 점수는 기본점수와 링크 점수의 합으로 구한다. ( scores[i][3] )
기본 점수 ( scores[i][0] )
기본점수는 약간의 꼼수(?)라고 해야될지 모르겠지만, 웹페이지에 해당하는 HTML문자열에서 "<body> ~ </body>" 부분에서만 찾아도 모든 테스트 케이스에 대해 통과한다. 이 부분은 의도한 부분인지는 잘 모르겠다.
word를 찾을 때 주의할 점은 다음과 같다.
- 검색어가 "test" 일때 "testtest" 의 경우는 일치하는게 없다고 생각한다.
- 검색어가 "test" 일때 "test9test" 의 경우는 2번 일치 한다고 생각한다.
- 단어는 알파벳을 제외한 모든 문자를 기준으로 구분 짓는다.
- 단어는 대문자와 소문자를 가리지 않는다. "test" 와 "TeSt"는 같은 걸로 취급한다.
위 4가지를 중점적으로 작성하면 쉽게 찾을 수 있다.
double findword(string input, string word)
{
string target1 = "<body>";
string target2 = "</body>";
int index1 = input.find(target1); index1 += target1.size();
int index2 = input.find(target2);
string tmp = input.substr(index1, index2 - index1);
string tmp2;
double cnt = 0;
for(int i=0; i<tmp.size(); i++)
{
char letter = tmp[i];
if(isAlphabet(letter))
{
tmp2.push_back(letter);
}
else
{
makeSmall(tmp2);
if(tmp2.compare(word) == 0) cnt++;
tmp2.clear();
}
}
return cnt;
}body 부분을 find함수를 이용해 찾고 substr를 이용해 잘라서 word를 찾는 방식이다.
외부 링크의 개수 ( scores[i][1] )
외부 링크의 개수를 찾는 방법도 word를 찾는 방법과 유사하다.
외부 링크는 다음과 같은 형태를 가진다 <a href ="링크"> 따라서 a href 이 부분을 찾아서 위의 링크를 추출해서 vector에다가 추가해주는 방식으로 외부링크들을 구할 수 있다.
vector<string> findOuterLink(string input)
{
vector<string> outerlinks;
string target = "<a href=\"https://";
int index = input.find(target);
while(index != input.npos)
{
index += target.size();
string tmp;
for(; input[index] != '\"'; index++)
{
tmp.push_back(input[index]);
}
outerlinks.push_back(tmp);
input = input.substr(index);
index = input.find(target);
}
return outerlinks;
}이때 링크의 끝은 끝 따옴표를 찾으면 종료하는 방식으로 작성하였다.
이때 링크의 개수는 한개가 아니라 여러개 일 수 있기 때문에 find를 이용해 첫번째 a href를 찾고, 링크를 추출한 다음 다음 a href 찾는 방식을 이용했고 종료조건은 target을 찾지 못 했을때 리턴되는 -1값을 이용하여 종료했다.
웹페이지 주소 찾기
다음으로 구해야 하는 것은 한 웹페이지로 링크가 걸린 다른 웹페이지의 (기본점수 / 외부 링크 의 수)의 총합을 구해야 한다.
이때 각 웹페이지 별로 주소를 알아야 어떤 웹페이지들끼리 연결되는지 알 수 있다.
따라서 각자의 주소를 알아야하는데, 이것도 외부 링크를 구하는 것과 같이 tag가 존재하기 때문에 쉽게 찾을 수 있다.
string findURL(string input)
{
string target = "<meta property=\"og:url\" content=\"https://";
int index = input.find(target); index += target.size();
string tmp;
for(int i=index; i<input.size(); i++)
{
if(input[i] == '\"') break;
else tmp.push_back(input[i]);
}
return tmp;
}다음과 같은 방법으로 각 웹페이지의 주소들을 찾을 수 있다.
이 주소들은 map 자료구조를 이용해 주소를 key로서 value는 인덱스로 저장하였다.
for(int i=0; i<pages.size(); i++)
{
makeSmall(pages[i]);
string cur_url = findURL(pages[i]);
mp[cur_url] = i;
scores[i][0] = findword(pages[i],word);
outerlinks[i] = findOuterLink(pages[i]);
scores[i][1] = outerlinks[i].size();
}
for(int i=0; i<pages.size(); i++)
{
for(int j=0; j<outerlinks[i].size(); j++)
{
if(mp.find(outerlinks[i][j]) == mp.end()) continue;
if(scores[i][1] == 0) scores[mp[outerlinks[i][j]]][2] = 0;
else scores[mp[outerlinks[i][j]]][2] += ((double)scores[i][0] / (double)scores[i][1]);
}
}
for(int i=0; i<pages.size(); i++)
{
scores[i][3] = scores[i][0] + scores[i][2];
}
각 page들 별로 현재url, 외부링크, 기본 점수를 구한 뒤 링크 점수와 매칭점수를 구할 수 있다.
다음으로는 가장 큰 매칭점수와 가장 큰 매칭점수를 갖는 인덱스가 여러개면 가장 작은 인덱스를 구하는 코드
double max_v = 0;
int max_index = 0;
for(int i=0; i<scores.size(); i++)
{
if(scores[i][3] > max_v)
{
max_v = scores[i][3];
max_index = i;
}
}
이때 중요한 점은 점수를 계산하는 배열과 매칭 점수의 최댓값을 찾을 때 double 자료형으로 구해야 제대로 구할 수 있다.
[전체 소스 코드]
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
bool isAlphabet(char letter)
{
if(letter >= 'a' && letter <= 'z') return true;
if(letter >= 'A' && letter <= 'Z') return true;
return false;
}
void makeSmall(string &input)
{
for(int i=0; i<input.size(); i++)
{
if(isAlphabet(input[i]) == false) continue;
if(input[i] >= 'a' && input[i] <= 'z') continue;
else
input[i] = input[i]+32;
}
}
string findURL(string input)
{
string target = "<meta property=\"og:url\" content=\"https://";
int index = input.find(target); index += target.size();
string tmp;
for(int i=index; i<input.size(); i++)
{
if(input[i] == '\"') break;
else tmp.push_back(input[i]);
}
return tmp;
}
double findword(string input, string word)
{
string target1 = "<body>";
string target2 = "</body>";
int index1 = input.find(target1); index1 += target1.size();
int index2 = input.find(target2);
string tmp = input.substr(index1, index2 - index1);
string tmp2;
double cnt = 0;
for(int i=0; i<tmp.size(); i++)
{
char letter = tmp[i];
if(isAlphabet(letter))
{
tmp2.push_back(letter);
}
else
{
makeSmall(tmp2);
if(tmp2.compare(word) == 0) cnt++;
tmp2.clear();
}
}
return cnt;
}
vector<string> findOuterLink(string input)
{
vector<string> outerlinks;
string target = "<a href=\"https://";
int index = input.find(target);
while(index != input.npos)
{
index += target.size();
string tmp;
for(; input[index] != '\"'; index++)
{
tmp.push_back(input[index]);
}
outerlinks.push_back(tmp);
input = input.substr(index);
index = input.find(target);
}
return outerlinks;
}
int solution(string word, vector<string> pages) {
int answer = 0;
map<string,int> mp;
vector<vector<double>> scores; scores.resize(pages.size());
for(int i=0; i<pages.size(); i++) scores[i].resize(4);
vector<vector<string>> outerlinks; outerlinks.resize(pages.size());
makeSmall(word);
for(int i=0; i<pages.size(); i++)
{
makeSmall(pages[i]);
string cur_url = findURL(pages[i]);
mp[cur_url] = i;
scores[i][0] = findword(pages[i],word);
outerlinks[i] = findOuterLink(pages[i]);
scores[i][1] = outerlinks[i].size();
}
for(int i=0; i<pages.size(); i++)
{
for(int j=0; j<outerlinks[i].size(); j++)
{
if(mp.find(outerlinks[i][j]) == mp.end()) continue;
if(scores[i][1] == 0) scores[mp[outerlinks[i][j]]][2] = 0;
else scores[mp[outerlinks[i][j]]][2] += ((double)scores[i][0] / (double)scores[i][1]);
}
}
for(int i=0; i<pages.size(); i++)
{
scores[i][3] = scores[i][0] + scores[i][2];
}
double max_v = 0;
int max_index = 0;
for(int i=0; i<scores.size(); i++)
{
if(scores[i][3] > max_v)
{
max_v = scores[i][3];
max_index = i;
}
}
return max_index;
}어렵지는 않았지만 구현하는데 살짝 힘든 부분이 있는 문제였던거 같다.
굳