프로그래머스 매칭 점수(2019 KAKAO BLIND RECRUITMENT)
문제 URL : https://programmers.co.kr/learn/courses/30/lessons/42893
코딩테스트 연습 - 매칭 점수
매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀
programmers.co.kr
문제 접근법 :
매칭점수를 계산해내는 방법은 매우쉬우니 생략하겠다 어렵다고하는건 문제를 제대로 읽지않은겁니다.
문제가 긴것일뿐 이해하기어려운것도 아니고 쉽다 다만 파싱하는것의 차이에서 어렵게 느끼게될뿐이지
처음 봤었을땐 어려울것같아서 문제만 대충흝어보고 안풀었던문제라
제대로 풀어보려고 정규표현식을 미리공부한다음에 오늘 풀었고
솔직히 쉽게 풀려서 나 자신도 놀랬다...
많은사람들이 실수를 했던것같지만 정규표현식을 책으로 제대로 공부했기에 별실수가 없었습니다.
우선 기본점수를 parsing하는 과정은 [a-zA-Z]+로 해당하는 모든 문자열들을 찾아 word와 함께
둘다 소문자로 바꾼다음 일치하는지
그리고 해당 페이지의 url을 찾는건
정규표현식으로 <meta property="og:url" content="(.*?)"\s*/>를 이용하면된다.
<meta property="og:url" content="(.*)"\s*/> 이렇게 하시는분이 있어서 틀리는분이 있는데
정규표현식의 게으른수량자를 모를것같아 설명하지만
<p>*.</p>로 html 문서를 검색했다고 가정해보자
<p>abcd</p> and <p>hi</p>가 있다면 어떻게 되는지 아시나요?
<p>abcd</p> and <p>hi</p>가전부 검색되버리는 오류가 있다 원하는건
<p>abcd</p> 와 <p>hi</p>일것이다 그렇기에
정규표현식 <p>*.?</p>로 바꿔주면
<p>abcd</p> and <p>hi</p>가 검색되어 원하는것이 검색되는것이 게으른 수량자 탐색방법입니다.
여기서 다른답들을 찾아봤지만
게으른 수량자가아닌 \S로 해결하는 코드들도 공백아닌 문자열들이 나오니 물론 좋지만
게으른 수량자를 공부해놓는것도 훨씬 좋을듯하다
그리고 마지막으로 외부링크도 마찬가지로
정규표현식 <a href="(.*?)"> 를이용하여 쉽게 구할수있습니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> basis, outer;
unordered_map<string, vector<string>> link;
string toLower(string& s) {
string res;
for (char c : s)
res += tolower(c);
return res;
}
string getAddress(string& page) {
string address = "<meta property=\"og:url\" content=\"(.*?)\"\\s*/>";
regex meta(address);
smatch match;
regex_search(page, match, meta);
return match[1];
}
int getBasis(string& page, string word) {
regex re("[a-zA-Z]+");
word = toLower(word);
sregex_iterator it(page.begin(), page.end(), re), end;
int cnt = 0;
while (it != end) {
string s = it->str();
s = toLower(s);
if (s == word)
cnt++;
it++;
}
return cnt;
}
vector<string> getOuters(string& page) {
string ref = "<a href=\"(.*?)\">";
regex re(ref);
sregex_token_iterator it(page.begin(), page.end(), re, 1), end;
return vector<string>(it, end);
}
int solution(string word, vector<string> pages) {
int answer = 0;
vector<pair<double, int>> res;
vector<string> av;
//기본점수 외부링크수
for (string page : pages) {
//해당 url
string address = getAddress(page);
av.push_back(address);
//기본점수
int base = getBasis(page, word);
//외부링크
vector<string> ov = getOuters(page);
basis[address] = base;
outer[address] = ov.size();
for (int i = 0; i < ov.size(); i++) {
link[ov[i]].push_back(address);
}
}
//매칭점수 결과
for (int i = 0; i < av.size(); i++) {
double matching = 0;
for (string s : link[av[i]]) {
matching += (double)basis[s] / (double)outer[s];
}
res.push_back({ -matching - basis[av[i]],i });
}
sort(res.begin(), res.end());
return res[0].second;
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 논리적인 오류등 댓글은 언제나 환영입니다.