> 문제
> 문제풀이
문제가 다소 복잡하다.
하나의 단어와 HTML 페이지 문자열들이 주어지며,
기본점수, 외부 링크 수, 링크점수를 구하여 여기서 말하는 매칭점수를 구해야 한다.
위 세가지만 찾으면 매칭점수는 그대로 연산하면 된다.
기본점수는 HTML 페이지에 포함하는 단어의 개수이다.
대소문자 무시하기 때문에 소문자로 통일하였다.(혹시 태그명을 단어로 쓰일지 몰라서 소문자로 사용)
외부 링크 수는 “<a href="“에 해당하는 문자열을 찾아서 구하였다.
링크점수는 해당 웹페이지가 링크로 걸린 다른 웹페이지의 기본점수 / 외부 링크 수의 총 합이며,
map 자료구조를 사용하여 외부 링크를 구할 때 미리 저장하여 사용하였다.
소스는 다음과 같다.
import java.util.*;
class Solution {
static class Info{
String url;
int index, point, links;
public Info(int index, int point, int links){
this.index = index;
this.point = point;
this.links = links;
}
}
static final String URL_TAG = "<meta property=\"og:url\" content=\"";
static final String A_TAG = "<a href=\"";
public int solution(String word, String[] pages) {
int wordLen = word.length();
Map<String, Info> infos = new HashMap<>();
Map<String, List<String>> matchs = new HashMap<>();
for(int i=0; i<pages.length; i++){
word = word.toLowerCase();
String page = pages[i].toLowerCase();
int point = 0;
int links = 0;
int start = 0;
// 기본점수 구하기.
int li = -1; // lowerIndex
while((li = page.indexOf(word, start)) != -1){
boolean flag = true;
if(li - 1 >= 0){
char frontChar = page.charAt(li - 1);
if(frontChar >= 'a' && frontChar <= 'z') flag = false;
}
if(li + wordLen < page.length()){
char backChar = page.charAt(li+wordLen);
if(backChar >= 'a' && backChar <= 'z') flag = false;
}
if(flag) point++;
start = li + 1;
}
// 웹페이지 url 찾기.
start = page.indexOf(URL_TAG) + URL_TAG.length();
StringBuilder url = new StringBuilder();
char c = ' ';
while((c = page.charAt(start++)) != '"'){
url.append(c);
}
// 모든 외부링크 찾기.
start = -1;
c = ' ';
StringBuilder href = null;
while((start = page.indexOf(A_TAG, start)) != -1){
start += A_TAG.length();
href = new StringBuilder();
while((c = page.charAt(start++))!= '"'){
href.append(c);
}
String hrefToString = href.toString();
if(matchs.get(hrefToString) == null) matchs.put(hrefToString, new ArrayList<>());
matchs.get(hrefToString).add(url.toString());
links++;
}
infos.put(url.toString(), new Info(i, point, links));
}
// 매칭점수 계산.
Iterator<String> it = infos.keySet().iterator();
int answer = Integer.MAX_VALUE;
double max = -1;
while(it.hasNext()){
String u = it.next();
Info info = infos.get(u);
double tmp = info.point;
if(matchs.get(u) != null) {
List<String> mList = matchs.get(u);
for(int i=0; i<mList.size(); i++){
Info tinfo = infos.get(mList.get(i));
tmp+=(tinfo.point/(double)tinfo.links);
}
}
if(max < tmp){
answer = info.index;
max = tmp;
}else if(max == tmp && answer > info.index) answer = info.index;
}
return answer;
}
}
문제 출처 : Programmers
PREVIOUS[프로그래머스] Level3 - 배달