programmers.co.kr/learn/courses/30/lessons/42893
코딩테스트 연습 - 매칭 점수
매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀
programmers.co.kr
문제 요약
- 검색어 word와 웹페이지의 HTML 목록인 pages가 주어졌을 때, 매칭점수가 가장 높은 웹페이지의 index를 구하는 문제 ( 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것 )
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있음
- 기본점수 = 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수 ( 대소문자 구분 안 함 )
- 외부 링크 수 = 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수
- 링크점수 = 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합
- 매칭점수 = 기본점수 + 링크점수
- 한 웹페이지의 url은 HTML의 <head> 태그 내에 <meta> 태그의 값으로 주어짐
<meta property=og:url content=“https://어쩌고” /> - 한 웹페이지에서 모든 외부 링크는 <a href=“https://어찌고“> 의 형태를 가짐
- 검색어를 찾을 때, 대소문자 구분은 무시하고 찾음
- 검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영
( 단어는 알파벳을 제외한 다른 모든 문자로 구분 )
<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>
문제 풀이
* 문자열
- 검색어 찾을 시 대소문자 구분 안하므로 전처리로 검색어( String word )를 소문자로 변환
- TreeMap 생성
- key ☞ 입력받은 웹페이지들을 탐색하며 현재 웹페이지( String pages[i] )의 url
- value ☞ 〃 idx
- Page class 생성
- 기본 점수( sb : score_basic ), 외부 링크 수( sle : score_link_ex ), 외부 링크의 인덱스를 담은 리스트( ue : url_ex )로 구성
- Page 배열( Page ps[] ) 생성 ( 크기는 웹페이지 수( = pages.length ) 만큼 )
- 문자열 안에서 패턴을 적용하여 원하는 부분을 추출하기 위해 Pattern, Matcher 사용 -- 정규식
- url ☞ "<meta property=\"og:url\" content=\"(https://[\\S]*)\""
- 외부 링크 ☞ "<a href=\"(https://[\\S]*)\">"
- 검색어 ☞ "(?<=[^a-z])"+word+"[^a-z]"
- 각각의 개수를 세고, Page 배열( ps[] )에 넣음
- ps[]를 탐색하며 ue를 통해 링크 점수( sl : score_link )와 매칭 점수( sm : score_matching )를 구하고, 매칭 점수의 최댓값을 갱신
- 매칭 점수가 가장 큰 웹페이지의 인덱스 리턴
import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Solution {
class Page {
int sb, sle; // score_basic, score_link_ex
List<Integer> ue; // url_ex
Page() {
ue = new ArrayList<>();
}
}
public int solution( String word, String[] pages ) {
word = word.toLowerCase();
int n = pages.length, i; // num_pages
int sb, sle, im_m = 0; // score_basic, score_link_ex, idx_matching_max
double sl, sm, sm_m = 0; // score_link, score_matching, score_matching_max
String u, ue; // url, url_ex
TreeMap<String, Integer> tm = new TreeMap<>(); // tree_map - url, idx
Page ps[] = new Page[n];
Matcher m;
for( i = 0; i < n; i++ ) {
m = Pattern.compile("<meta property=\"og:url\" content=\"(https://[\\S]*)\"").matcher( pages[i] );
while( m.find() ) {
u = m.group(1);
ps[i] = new Page();
tm.put( u, i );
}
}
for( i = 0; i < n; i++ ) {
sle = 0;
m = Pattern.compile("<a href=\"(https://[\\S]*)\">").matcher( pages[i] );
while( m.find() ) {
sle++;
ue = m.group(1);
if( tm.containsKey( ue ) )
ps[tm.get( ue )].ue.add( i );
}
ps[i].sle = sle;
}
for( i = 0; i < n; i++ ) {
sb = 0;
m = Pattern.compile("(?<=[^a-z])"+word+"[^a-z]").matcher( pages[i].toLowerCase() );
while( m.find() ) {
System.out.println( m.group() );
sb++;
}
ps[i].sb = sb;
}
for( i = 0; i < n; i++ ) {
sl = 0;
for( Integer ile : ps[i].ue )
sl += (double)ps[ile].sb / ps[ile].sle;
sm = ps[i].sb + sl;
if( sm_m < sm ) {
sm_m = sm;
im_m = i;
}
}
return im_m;
}
}
'코딩 문제 풀기 ( Algorithm problem solving ) > 프로그래머스 ( Programmers )' 카테고리의 다른 글
| [프로그래머스(Programmers)][자바(java)] (Lv3) 외벽 점검 (0) | 2021.02.19 |
|---|---|
| [프로그래머스(Programmers)][자바(java)] (Lv3) 자물쇠와 열쇠 (0) | 2021.02.19 |
| [프로그래머스(Programmers)][자바(java)] (Lv3) 길 찾기 게임 (0) | 2021.02.17 |
| [프로그래머스(Programmers)][자바(java)] (Lv3) 셔틀버스 (0) | 2021.02.17 |
| [프로그래머스(Programmers)][자바(java)] (Lv3) 추석 트래픽 (0) | 2021.02.17 |