ALGORITHM/PROGRAMMERS
[프로그래머스] 매칭 점수 (2019 KAKAO BLIND RECRUITMENT)
0298
2021. 3. 29. 21:38
programmers.co.kr/learn/courses/30/lessons/42893
코딩테스트 연습 - 매칭 점수
매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀
programmers.co.kr
2021-03-29
|
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Solution42893 {
static class Link {
int index;
int base;
int out;
double linked;
public Link(int index, int base, int out, double linked) {
this.index = index;
this.base = base;
this.out = out;
this.linked = linked;
}
}
public static String extractBody(String word) { // body 추출
Pattern bodyPt = Pattern.compile("<body>(?s)(.*)</body>"); // <body>와 </body> 태그 사이에 있는 문장 추출
Matcher bodyMat = bodyPt.matcher(word);
String body = "";
if (bodyMat.find()) {
body = bodyMat.group(1);
}
return body;
}
public static int solution(String word, String[] pages) {
int answer = 987654321;
word = word.toLowerCase();
HashMap<String, Link> map = new HashMap<>();
String[] names = new String[pages.length];
for (int i = 0; i < pages.length; i++) {
// url 추출
Pattern urlPt = Pattern.compile("<meta property=\"og:url\" content=\"https://(\\S*)\""); // url extract
Matcher urlMat = urlPt.matcher(pages[i]);
String url = "";
if (urlMat.find()) {
url = urlMat.group(1);
}
// body 부분 추출
String body = extractBody(pages[i]);
// 외부 링크 수 count
Pattern aPt = Pattern.compile("<a href="); // <a href= 개수
Matcher aMat = aPt.matcher(body);
int aCnt = 0;
while (aMat.find()) {
aCnt++;
}
// 검색어 등장 횟수
body = body.toLowerCase();
int srchCnt = 0;
int index = 0;
while (true) {
index = body.indexOf(word, index + 1);
if (index < 0) break;
char prev = body.charAt(index - 1);
char post = body.charAt(index + word.length());
if (!Character.isLetter(prev) && !Character.isLetter(post)) { // 양쪽 모두 글자가 아니어야함
srchCnt++;
}
}
map.put(url, new Link(i, srchCnt, aCnt, 0.0));
names[i] = url;
}
for (int i = 0; i < pages.length; i++) {
String body = extractBody(pages[i]);
// 링크 점수
Pattern aPt = Pattern.compile("<a href=\"https://(\\S*)\""); // <a href= 링크 개수
Matcher aMat = aPt.matcher(body);
String aUrl = "";
while (aMat.find()) {
aUrl = aMat.group(1);
Link origin = map.get(names[i]);
if (map.get(aUrl) != null && origin.base != 0 && origin.out != 0) {
double link = (double) origin.base / (double) origin.out;
Link tmp = map.get(aUrl);
tmp.linked += link;
map.put(aUrl, tmp);
}
}
}
//큰 매칭 값 찾기
Iterator<String> keys = map.keySet().iterator();
double value = 0.0;
while (keys.hasNext()) {
String next = keys.next();
double matching = map.get(next).base + map.get(next).linked;
if (value <= matching) {
if (value == matching) answer = Math.min(answer, map.get(next).index);
else answer = map.get(next).index;
value = matching;
}
}
return answer;
}
public static void main(String[] args) {
// String w = "blind";
// String[] p = {"<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@blINd 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>\nSuspendisblINdse potenti. Vivamus venenatis tellus non turpis bibendum, \neiei<a href=\"https://a.com\"> Link to a Blind </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>"};
String w = "Muzi";
String[] p = {"<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>#!0muzi0muzi0!)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>"};
System.out.println(solution(w, p));
}
}
|
cs |
#문제풀이
생각보다 되게 오래 걸렸었던 문제이다. 그만큼 코드도 깔끔하지는 못하다,,,
1. line 38 ~ : url 추출하는 패턴을 사용했다. 맨처음 key값이 될 수 있는 url을 추출하였다. <meta ~ 로 시작하여 content 안에 있는 글자를 추출하였다.
2. line 45 ~ + extractBody() : body 부분을 추출했다. <body>와 </body> 사이를 추출했다. 나중에 한 번 더 사용하려고 따로 빼서 사용했다.
3. line 47 ~ : 외부 링크 수를 count 했다. 단순히 <a href=로 시작하는 것의 개수를 세었다. (외부 링크 수 : 현재 페이지에서 외부로 연결된 링크 수)
4. line 54 ~ : lowercase로 바꾼 후 검색어 등장 횟수를 체크했다. 찾고자 하는 word의 index를 찾은 후 그 word index의 앞과 word index + word.length의 뒤를 살펴 보았을 때 둘 다 글자가 아닌 경우 완벽하게 한 단어로 추출 할 수 있는 것이므로, 이 조건을 만족한 경우 수를 세주었다. (기본점수 : 찾고자 하는 글자 수)
5. 위에 1~4번을 이용해서 url key 값을 뽑아내었고, 기본점수, 외부 링크 수를 계산하여 value값에 넣었다.
6. line 70 ~ : body를 다시 한 번 추출해서, <a href=의 링크를 뽑아내었다. 위에서 key 값을 모두 뽑아내었으므로, 뽑아낸 링크가 key값에 존재하는 경우 그리고 기본 점수와 외부 링크 수가 0이 아닌 경우 링크 점수를 계산해주고 map에 추가해주었다. (링크 점수 : 다른 웹 페이지에서 해당 웹페이지로 외부 링크가 걸렸을 때, 그 다른 웹페이지의 기본점수 / 외부 링크 수)
7. line 89~ : 만들어놓은 map을 돌면서 매칭 점수(기본 점수 + 링크 점수)를 계산 해주었다. index 값을 애초에 들고 다녔으므로 그냥 단순하게 index 값도 매칭점수 값 비교할 때 함께 비교했다.