728x90
https://programmers.co.kr/learn/courses/30/lessons/42893
코딩테스트 연습 - 매칭 점수
매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀
programmers.co.kr
// 코드
|
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
|
import java.util.*;
class Solution {
// 인덱스 번호를 키로하여 페이지 정보를 가진다.
class Page {
// index
int idx;
// 기본점수, 외부 링크 수
int basic, link;
// 매칭점수
double score;
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;
}
}
// main
public int solution(String word, String[] pages) {
// 페이지를 url을 key, idx를 value로 관리한다.
Map<String, Integer> pageMap = new HashMap<>();
// Page를 리스트로 관리한다.
List<Page> pageList = new ArrayList<>();
// 편의를 위해 미리 word의 길이를 구해둔다.
int wsize = word.length();
// 대소문자를 구분하지 않으므로 소문자로 변환한다.
word = word.toLowerCase();
// pages를 순회하며 "URL추출, 검색어 추출, 외부 링크수"를 구한다.
for(int i=0; i<pages.length; ++i) {
// 대소문자를 구분하지 않으므로 웹페이지 문자를 모두 소문자로 변환한다.
String s = pages[i] = pages[i].toLowerCase();
// 원하는 값을 추출하기위해 좌표 정보를 관리한다.
int mid = 0, posLeft = 0, posRight = 0;
// 1. URL 추출
while(mid <= posLeft) {
posLeft = s.indexOf("<meta", posLeft + 1);
posRight = s.indexOf(">", posLeft);
mid = s.lastIndexOf("https://", posRight);
}
posRight = s.indexOf("\"", mid);
String url = s.substring(mid, posRight);
// 2. 일치하는 검색어를 <body>이후로 검색하여 추출하여 개수를 구한다. 개수는 기본점수 해당된다.
posLeft = s.indexOf("<body>", posRight);
int basic = 0; // 기본점수
for(int start = posLeft; ; ) {
start = s.indexOf(word, start + 1);
// 일치하는 검색어가 없는경우
if( start == -1 ) break;
// 찾고자하는 단어의 앞과 뒤에 '숫자/공백/특수기호'가 아닌 문자가 오는경우는 해당하지 않으므로 필터링
if( Character.isLetter(s.charAt(start - 1)) || Character.isLetter(s.charAt(start + wsize))) continue;
basic++;
start += wsize;
}
// 3. 외부 링크수 : body태그를 기준으로 다시 검색한다. 하지만 여기서는 어느 페이즈를 지칭하는지는 알 수 없다.
int link = 0;
for(int start = posLeft; ; ) {
start = s.indexOf("<a href", start + 1);
if(start == -1) break;
link++;
}
// url과 인덱스를 넣어준다.
pageMap.put(url, i);
// 페이지의 정보를 담아 pageList에 넣어준다.
pageList.add(new Page(i, basic, link, (double)basic));
}
// 매칭 점수 구하기
for(int i=0; i<pages.length; ++i) {
String s = pages[i];
for(int posLeft=0, posRight=0; ; ) {
posLeft = s.indexOf("<a href", posRight);
if(posLeft == -1) break;
// a태그 기준으로 url추출.
posLeft = s.indexOf("https://", posLeft);
posRight = s.indexOf("\"", posLeft);
String linkUrl = s.substring(posLeft, posRight);
// 추출한 url이 pageMap에 있는지 체크
Integer value = pageMap.get(linkUrl);
// 있다면 매칭 점수를 넣어준다.
if(value != null) pageList.get(value).score += (double)pageList.get(i).basic / pageList.get(i).link;
}
}
pageList.sort(new Comp());
return pageList.get(0).idx;
}
}
|
cs |
반응형
'CS > 알고리즘_KAKAO BLIND RECRUITMENT' 카테고리의 다른 글
| 2018 KAKAO BLIND RECRUITMENT : [3차] n진수 게임 (0) | 2021.11.01 |
|---|---|
| 2018 KAKAO BLIND RECRUITMENT : [1차] 다트 게임 (0) | 2021.10.29 |
| 2018 KAKAO BLIND RECRUITMENT[1차] 뉴스 클러스터링 (0) | 2021.10.27 |
| 2021 KAKAO BLIND RECRUITMENT : 매출 하락 최소화 (0) | 2021.10.26 |
| 2021 KAKAO BLIND RECRUITMENT : 순위 검색(비트마스크 & 집합) (0) | 2021.10.25 |