[C++로 풀이] 매칭 점수⭐⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 매칭 점수
난이도 ⭐⭐⭐
🚀 문제
["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://a.com\"/>\n</head> \n<body>\nBlind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. \n<a href=\"https://b.com\"> Link to b </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://b.com\"/>\n</head> \n<body>\nSuspendisse potenti. Vivamus venenatis tellus non turpis bibendum, \n<a href=\"https://a.com\"> Link to a </a>\nblind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.\n<a href=\"https://c.com\"> Link to c </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://c.com\"/>\n</head> \n<body>\nUt condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind\n<a href=\"https://a.com\"> Link to a </a>\n</body>\n</html>"]
["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://careers.kakao.com/interview/list\"/>\n</head> \n<body>\n<a href=\"https://programmers.co.kr/learn/courses/4673\"></a>#!MuziMuzi!)jayg07con&&\n\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://www.kakaocorp.com\"/>\n</head> \n<body>\ncon%\tmuzI92apeach&2<a href=\"https://hashcode.co.kr/tos\"></a>\n\n\t^\n</body>\n</html>"]
🚀 내 풀이 ⭕
문제에서 요구한대로 구현만 하면 되는 문제라 어렵진 않았지만 그만큼 챙겨야할 조건들이 많아 까다로운 문제이기도 했다. 코드도 짱 길다..
#include <string>
#include <vector>
using namespace std;
/* 한 페이지의 데이터 */
struct Data {
string my_url; // 이 페이지의 링크
vector<string> link; // 이 페이지의 외부 링크들
string text; // 이 페이지의 텍스트들 (HTML 문법 제외 <Body>태그 안에 있는 일반 텍스트)
};
/* 한 페이지의 점수 */
struct Score {
int basic; // 기본점수
int outer_link; // 외부링크 수
double link; // 링크점수
double matching; // 매칭점수
};
int solution(string word, vector<string> pages) {
int answer = 0;
vector<Data> data(pages.size()); // 페이지들 별로 데이터(링크, 외부링크, 텍스트)를 담을 배열
vector<Score> scores(pages.size()); // 페이지들 별로 4가지 종류의 점수를 담을 배열
for (int i = 0; i < word.length(); ++i)
word[i] = tolower(word[i]); // 대소문자 구분하지 않으니 word 도 모두 소문자로 변환
/* 이 페이지의 링크 저장 */
const string mlink1 = "<meta property=\"og:url\" content=\"https://";
const string mlink2 = "\"";
for (int i = 0; i < pages.size(); ++i) {
int start = pages[i].find(mlink1);
int end = pages[i].find(mlink2, start + mlink1.length());
int len = end - (start + mlink1.length());
data[i].my_url = pages[i].substr(start + mlink1.length(), len);
}
/* 이 페이지의 외부 링크들 저장 */
const string olink1 = "<a href=\"https://";
const string olink2 = "\">";
for (int i = 0; i < pages.size(); ++i) {
int start = 0;
int end = 0;
while (true) {
start = pages[i].find(olink1, end + olink2.length());
if (start == string::npos) break;
end = pages[i].find(olink2, start + olink1.length());
int len = end - (start + olink1.length());
data[i].link.push_back(pages[i].substr(start + olink1.length(), len));
}
}
/* 이 페이지의 텍스트들 저장 */
const string body_start = "<body>";
const string body_end = "</body>";
for (int i = 0; i < pages.size(); ++i) {
int start = pages[i].find(body_start);
int end = pages[i].find(body_end);
int len = end - (start + body_start.length());
string body = pages[i].substr(start + body_start.length(), len);
bool aTag = false;
string str = "";
for (int j = 0; j < body.length(); ++j) {
if (body[j] == '<') {
aTag = true;
continue;
}
if (body[j] == '>') {
aTag = false;
continue;
}
if (aTag == false)
str += body[j];
}
data[i].text = str;
}
/* 1. 기본 점수 구하기 */
for (int i = 0; i < data.size(); ++i) {
// 대문자는 소문자로 바꾸고 알파벳이 아닌 문자는 모두 공백으로
for (int j = 0; j < data[i].text.length(); ++j) {
if (data[i].text[j] >= 'A' && data[i].text[j] <= 'Z')
data[i].text[j] = tolower(data[i].text[j]);
if (data[i].text[j] >= 'a' && data[i].text[j] <= 'z')
continue;
data[i].text[j] = ' ';
}
// 공백을 기준으로, 즉 단어 단위로 파싱하여 벡터에 저장
vector<string> v_temp;
string temp = "";
for (int j = 0; j < data[i].text.length(); ++j) {
if (data[i].text[j] == ' ') {
v_temp.push_back(temp);
temp = "";
continue;
}
temp += data[i].text[j];
}
v_temp.push_back(temp); // 이거 안해주면 마지막 단어는 벡터에 추가되지 않는다! (공백 만날때만 추가하게 해놔가지고..)
// 기본점수 카운팅
scores[i].basic = 0.0;
for (int j = 0; j < v_temp.size(); ++j)
if (v_temp[j] == word)
scores[i].basic++;
}
/* 2. 외부 링크 수 구하기 */
for (int i = 0; i < data.size(); ++i)
scores[i].outer_link = data[i].link.size();
/* 3. 링크 점수 구하기 */
for (int i = 0; i < data.size(); ++i) {
scores[i].link = 0.0;
for (int j = 0; j < data.size(); ++j) {
for (int k = 0; k < data[j].link.size(); ++k) {
if (data[i].my_url == data[j].link[k])
scores[i].link += (double)scores[j].basic / scores[j].outer_link;
}
}
}
/* 4. 매칭 점수 구하기 (+ 최대 매칭 점수)*/
double max = 0.0;
for (int i = 0; i < data.size(); ++i) {
scores[i].matching = scores[i].basic + scores[i].link;
if (max < scores[i].matching) {
max = scores[i].matching;
answer = i;
}
}
return answer;
}
🔥 전처리 단계
1️⃣ word 소문자로 변환
for (int i = 0; i < word.length(); ++i)
word[i] = tolower(word[i]);
검색어는 대소문자를 무시하고 찾기 때문에 검색어 word 또한 모두 소문자로 변환해주어야 한다. “Hello”는 “hello”가 될 수 있도록!
2️⃣ 페이지 별 “링크” 저장 (+테스트케이스 9번 에러 이유)
/* 이 페이지의 링크 저장 */
const string mlink1 = "<meta property=\"og:url\" content=\"https://";
const string mlink2 = "\"";
for (int i = 0; i < pages.size(); ++i) {
int start = pages[i].find(mlink1);
int end = pages[i].find(mlink2, start + mlink1.length());
int len = end - (start + mlink1.length());
data[i].my_url = pages[i].substr(start + mlink1.length(), len);
}
start: “<meta property="og:url" content="https://” 의 시작 위치를 담을 변수- 이 문자열의 처음 문자인 meta 태그를 여는
<의 인덱스가 담기게 된다.
- 이 문자열의 처음 문자인 meta 태그를 여는
end: “\"”의 시작 위치를 담을 변수 (즉 주소의 닫는 따옴표의 위치)- 처음엔 “"/>” 의 위치를 찾도록 하였는데 이러니까 테스트케이스 9번만 틀렸다. 왜냐하면 meta 태그에 다른 속성들이 또 있을 수 있기 때문이다. 예를 들어
"<meta property=\"og:url\" content=\"https://" hello = hello이렇게 링크 뒤에 다른 속성이 더 붙을 수도 있는 것이다. 즉content속성이 꼭 meta 태그의 마지막에 위치하리란 법은 없다. 따라서 pages[i].find(mlink2, start + mlink1.length()) 즉, 링크 주소의 시작 위치 이후부터 주소를 끝맺을 때 등장하는 따옴표\"를 찾게끔만 해주면 된다. (\"은 많이 등장하기 때문에start처럼 찾는 범위를pages[i]전체 범위로 하면 안된다.- 이렇게 9번만 틀리던 것을 해결하였다. (질문하기 탭에서 어떤 고마운 분께서 남겨주신 조언이였다.ㅠㅠㅠ)
- 처음엔 “"/>” 의 위치를 찾도록 하였는데 이러니까 테스트케이스 9번만 틀렸다. 왜냐하면 meta 태그에 다른 속성들이 또 있을 수 있기 때문이다. 예를 들어
len: 링크 주소의 길이- 링크 주소 문자열만
substr함수로 추출할건데 이 함수는 부분 문자열의 길이를 파라미터로 요구하기 때문에 링크 주소의 길이를 구해주었다.- 링크의 시작 위치 : start + mlink1.length()
- 링크의 끝 위치 : end
- 링크 주소 문자열만
3️⃣ 페이지 별 “외부링크”들 저장
/* 이 페이지의 외부 링크들 저장 */
const string olink1 = "<a href=\"https://";
const string olink2 = "\">";
for (int i = 0; i < pages.size(); ++i) {
int start = 0;
int end = 0;
while (true) {
start = pages[i].find(olink1, end + olink2.length());
if (start == string::npos) break;
end = pages[i].find(olink2, start + olink1.length());
int len = end - (start + olink1.length());
data[i].link.push_back(pages[i].substr(start + olink1.length(), len));
}
}
외부 링크는 여러개가 있을 수 있다. 따라서 "<a href=\"https://" 가 더 이상 없을 떄까지 while 문 내에서 계속 외부링크를 찾는다.(a href 태그) 외부 링크 문자열들을 link 벡터에 차례로 저장한다.
난 처음에 외부 링크를 저장하는 컨테이너를 vector가 아닌 해시맵(unordered_set)을 썼었다. unordered_set은 중복을 자동으로 제거해주는데, 사실 동일한 사이트의 외부 링크가 여러개일 수도 있다. 즉, 한 페이지에 a.com 링크가 여러번 등장할 수도 있는 것이다. 그럼 외부링크도 여러개일텐데, 해시맵을 사용하면 a.com가 한번 등장했다는 것으로 처리되므로 외부링크 수가 1 개로 처리될 수 있다. 이런 생각이 들어서 vector 로 컨테이너를 바꾸었다.
4️⃣ 페이지 별 “텍스트”들 저장
/* 이 페이지의 텍스트들 저장 */
const string body_start = "<body>";
const string body_end = "</body>";
for (int i = 0; i < pages.size(); ++i) {
int start = pages[i].find(body_start);
int end = pages[i].find(body_end);
int len = end - (start + body_start.length());
string body = pages[i].substr(start + body_start.length(), len);
bool aTag = false;
string str = "";
for (int j = 0; j < body.length(); ++j) {
if (body[j] == '<') {
aTag = true;
continue;
}
if (body[j] == '>') {
aTag = false;
continue;
}
if (aTag == false)
str += body[j];
}
data[i].text = str;
}
<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>
위 텍스트는 “Link to a”, “Link to c” 까지 포함하여, “Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum, Link to a blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut. Link to c” 가 되야 한다. <a href="https://a.com">와 <a href="https://c.com">는 검색어 탐색 범위가 되지 못한다.
- 텍스트는
<body>태그 안에 있다. <a>태그의 속성값들은 검색어 찾는 범위가 되지 못한다.<a href="https://a.com">와<a href="https://c.com">는 검색어 탐색 범위가 안디ㅏ.
- 1️⃣ 텍스트는
<body>태그 안에 있으므로<body>의 시작 위치와 끝을 찾는다.start시작 위치,end끝 위치,len는<body>태그 안에 있는 모든 텍스트의 길이- 최종적으로
body에<body>태그 내부에 있는 텍스트들이 담기게 한다.- 일단
<a href="https://a.com">와<a href="https://c.com">도 포함되어있긴 한 상태. 이제 이건 텍스트가 아닌걸로 걸러내야 한다.
- 일단
- 2️⃣ 외부링크
<a href>,</a>태그는 텍스트에서 제외<문자가 등장하면 a 태그가 시작되었다고 판단하고str에 문자를 덧붙이지 않기 위해 플래그 상태를 바꿈.(aTag)<a href의<던,</a>의<던 둘 다 해당
>문자가 등장하면 a 태그가 끝났다고 판단하고 이제str에 문자를 덧붙이기 위해 플래그를 상태를 바꿈 (aTag)<a href의>던,</a>의>던 둘 다 해당
- 최종적으로
str에 “Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum, Link to a blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut. Link to c” 가 담긴다.
🔥 점수 구하기
1️⃣ 기본 점수
/* 1. 기본 점수 구하기 */
for (int i = 0; i < data.size(); ++i) {
// 대문자는 소문자로 바꾸고 알파벳이 아닌 문자는 모두 공백으로 바꾸기
for (int j = 0; j < data[i].text.length(); ++j) {
if (data[i].text[j] >= 'A' && data[i].text[j] <= 'Z')
data[i].text[j] = tolower(data[i].text[j]);
if (data[i].text[j] >= 'a' && data[i].text[j] <= 'z')
continue;
data[i].text[j] = ' ';
}
// 공백을 기준으로, 즉 단어 단위로 파싱하여 벡터에 저장
vector<string> v_temp;
string temp = "";
for (int j = 0; j < data[i].text.length(); ++j) {
if (data[i].text[j] == ' ') {
v_temp.push_back(temp);
temp = "";
continue;
}
temp += data[i].text[j];
}
v_temp.push_back(temp); // 이거 안해주면 마지막 단어는 벡터에 추가되지 않는다! (공백 만날때만 추가하게 해놔가지고..)
// 기본점수 카운팅
scores[i].basic = 0.0;
for (int j = 0; j < v_temp.size(); ++j)
if (v_temp[j] == word)
scores[i].basic++;
}
기본 점수는 검색어가 포함된 횟수이다. 근데 검색어 포함 기준은 “단어 기준”이며, 단순 공백 기준 뿐만 아니라 그냥 알파벳이 아닌 문자가 사이에 있으면 단어라고 판단된다. “abc@abc” 는 “abc” 단어가 2 개 있는 것으로 판단된다.
전처리의 4️⃣과정에서 추출한 “텍스트” 에서 검색어 찾기
- 대소문자 구분 안하므로 먼저 대문자는 소문자로 변환
- 알파벳이 아닌건 모두 공백으로 변환
- 공백을 기준으로 단어로 파싱하여 임시 벡터에 단어별로 저장해둔다.
- 이 임시 벡터에서 검색어
word와 일치하는 단어를 찾는다. 찾았다면 점수 1씩 증가
2️⃣ 외부링크 수
/* 2. 외부 링크 수 구하기 */
for (int i = 0; i < data.size(); ++i)
scores[i].outer_link = data[i].link.size();
간단하게, 페이지별로 외부링크들을 벡터에 저장해두었으므로 벡터의 사이즈만 대입해주면 됨.
3️⃣ 링크 점수
/* 3. 링크 점수 구하기 */
for (int i = 0; i < data.size(); ++i) {
scores[i].link = 0.0;
for (int j = 0; j < data.size(); ++j) {
for (int k = 0; k < data[j].link.size(); ++k) {
if (data[i].my_url == data[j].link[k])
scores[i].link += (double)scores[j].basic / scores[j].outer_link;
}
}
}
나눗셈 과정에서 소수점이 발생할 수 있으므로 double로 선언하였다. data[i] 페이지의 링크(my_url)가 다른 모든 페이지들의 외부 링크 페이지들에 속해있나 보고 연산하면 된다. 입력 크기가 적어서(최대 20개에 문자열 길이 최대 1500자) 시간초과 안나고 연산시간도 나쁘지 않았다. 입력 크기가 더 커진다면 이렇게 구하면 안될듯 하다.
4️⃣ 매칭 점수
double max = 0.0;
for (int i = 0; i < data.size(); ++i) {
scores[i].matching = scores[i].basic + scores[i].link; // 매칭점수 = 기본점수 + 링크점수
if (max < scores[i].matching) {
max = scores[i].matching;
answer = i;
}
}
정답 인덱스 answer에 저장!
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기