6. 매칭 점수
- 정답률: 6.12%
- 문제 풀러 가기
프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다. 그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
- 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
- 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
- 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
- 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
예를 들어, 다음과 같이 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 이다.
- https://careers.kakao.com/index” />
- 한 웹페이지에서 모든 외부 링크는 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을 리턴하면 된다.
입출력 예 #1
- null
- word : blind
- pages :["http://www.w3.org/1999/xhtml\">\n\n\n\n \n\nBlind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. \n Link to b \n\n", "http://www.w3.org/1999/xhtml\">\n\n\n\n \n\nSuspendisse potenti. Vivamus venenatis tellus non turpis bibendum, \n Link to a \nblind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.\n Link to c \n\n", "http://www.w3.org/1999/xhtml\">\n\n\n\n \n\nUt condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind\n Link to a \n\n"]
- pages는 다음과 같이 3개의 웹페이지에 해당하는 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://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> <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>
위의 예를 가지고 각각의 점수를 계산해보자.
- 기본점수 및 외부 링크수는 아래와 같다.
- a.com의 기본점수는 3, 외부 링크 수는 1개
- b.com의 기본점수는 1, 외부 링크 수는 2개
- c.com의 기본점수는 1, 외부 링크 수는 1개
- 링크점수는 아래와 같다.
- a.com의 링크점수는 b.com으로부터 0.5점, c.com으로부터 1점
- b.com의 링크점수는 a.com으로부터 3점
- c.com의 링크점수는 b.com으로부터 0.5점
- 각 웹 페이지의 매칭 점수는 다음과 같다.
- a.com : 4.5 점
- b.com : 4 점
- c.com : 1.5 점
따라서 매칭점수가 제일 높은 첫번째 웹 페이지의 index인 0을 리턴 하면 된다.
입출력 예 #2
- word : Muzi
- pages :["http://www.w3.org/1999/xhtml\">\n\n\nhttps://careers.kakao.com/interview/list\"/>\n \n\nhttps://programmers.co.kr/learn/courses/4673\">#!MuziMuzi!)jayg07con&&\n\n\n", "http://www.w3.org/1999/xhtml\">\n\n\nhttps://www.kakaocorp.com\"/>\n \n\ncon%\tmuzI92apeach&2https://hashcode.co.kr/tos\">\n\n\t^\n\n"]
- pages는 다음과 같이 2개의 웹페이지에 해당하는 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://careers.kakao.com/interview/list"/> </head> <body> <a href="https://programmers.co.kr/learn/courses/4673"></a>#!MuziMuzi!)jayg07con&& </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://www.kakaocorp.com"/> </head> <body> con% muzI92apeach&2<a href="https://hashcode.co.kr/tos"></a> ^ </body> </html>
- 기본점수 및 외부 링크수는 아래와 같다.
- careers.kakao.com/interview/list 의 기본점수는 0, 외부 링크 수는 1개
- www.kakaocorp.com 의 기본점수는 1, 외부 링크 수는 1개
- 링크점수는 아래와 같다.
- careers.kakao.com/interview/list 의 링크점수는 0점
- www.kakaocorp.com 의 링크점수는 0점
- 각 웹 페이지의 매칭 점수는 다음과 같다.
- careers.kakao.com/interview/list : 0점
- www.kakaocorp.com : 1 점
따라서 매칭점수가 제일 높은 두번째 웹 페이지의 index인 1을 리턴 하면 된다.
2019 KAKAO 1차 온라인 테스트 6번 문제인 매칭 점수이다.
5번 문제는 순조롭게 풀려서 기분이 좋았는데 이 문제에서 고생을 많이했다...
정규식을 사용해서 풀어보려고 많은 시간 노력했지만 결국 70점을 끝으로 실패하고
인터넷에서 해답을 찾아보고 공부했다.
https://www.youtube.com/watch?v=F3Bfy3bKHc8
이 강의를 통해 해답을 봤으며 친절하고 천천히 알려주셔서 해답을 이해할 수 있었다.
꼭 복습을 해야하는 문제이고 내가 문자열을 처리하는 부분이 약하다는 것을 깨달았다.
문자열 처리하는 예제를 많이 공부해봐야겠다.
|
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
public class Solution {
class Page {
int idx;
int basic, link;
double score;
public Page(int idx, int basic, int link, double score) {
this.idx = idx;
this.basic = basic;
this.link = link;
this.score = score;
}
}
class Comp implements Comparator<Page>{
public int compare(Page a, Page b) {
if(a.score == b.score) {
return a.idx - b.idx;
} else if(a.score < b.score) {
return 1;
} else {
return -1;
}
}
}
public int solution(String word, String[] pages) {
int wsize = word.length();
Map<String, Integer>pageMap = new HashMap<>();
List<Page> pageList = new ArrayList<>();
word = word.toLowerCase();
for(int i=0; i<pages.length; i++) {
StringBuilder sb = new StringBuilder(pages[i].toLowerCase());
int mid = 0, posl = 0, posr = 0;
while(mid <= posl) {
posl = sb.indexOf("<meta", posl+1); // +1 을해야 똑같은걸 안찾는다.
posr = sb.indexOf(">", posl);
mid = sb.lastIndexOf("https://", posr); //뒤에서부터 찾는다.
}
posr = sb.indexOf("\"", mid);
String url = sb.substring(mid, posr);
posl = sb.indexOf("<body>", posr);
int basic = 0;
for(int start = posl; ;) {
start = sb.indexOf(word, start+1);
if(start < 0) break;
if(!Character.isLetter(sb.charAt(start-1)) && !Character.isLetter(sb.charAt(start+wsize))) {
basic++;
start += wsize;
}
}
int link = 0;
for(int start = posl; ;) {
start = sb.indexOf("<a href", start+1);
if(start < 0) break;
link++;
}
pageList.add(new Page(i, basic, link, (double)basic));
}
for(int i=0; i<pages.length; i++) {
StringBuilder sb = new StringBuilder(pages[i].toLowerCase());
for(int posl = 0, posr = 0; ;) {
posl = sb.indexOf("<a href", posr);
if(posl < 0) break;
posl = sb.indexOf("https://", posl);
posr = sb.indexOf("\"", posl);
String linkurl = sb.substring(posl, posr);
Integer value = pageMap.get(linkurl);
if(value != null) {
}
}
}
pageList.sort(new Comp());
}
}
|
'Algorithm' 카테고리의 다른 글
| 백준 15686 치킨 배달 Java (0) | 2019.09.13 |
|---|---|
| 백준 14500 테트로미노 Java (0) | 2019.09.11 |
| 백준 2293 동전 1 Java (0) | 2019.09.02 |
| 2019 KAKAO 후보키 Java (0) | 2019.08.27 |
| 2019 KAKAO 실패율 Java (0) | 2019.08.26 |