문제
핵심
-
html 문자열 파싱 문제이다. 웹 페이지들의 매칭 점수를 구한 뒤 가장 큰 매칭 점수를 가진 웹 페이지 인덱스를 출력한다. 매칭 점수는 기본 점수와 링크 점수의 합으로 계산하며, 기본 점수는 해당 웹 페이지의 텍스트 중 검색어가 등장하는 횟수이다. 링크 점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본 점수 / 외부 링크 수의 총합으로 구할 수 있다.
-
기본 점수는 메시지 body 부분을 잘라낸 후 body에서 word가 몇 개 있는지 세어 확인할 수 있다.
-
링크 점수는 각 페이지를 순회하며 해당 페이지에서 외부로 링크된 모든 페이지를 확인하면서, 외부 링크된 각 페이지에 현재 페이지의 기본 점수를 외부 링크 수로 나눈 값을 더하여 구할 수 있다.
for (int i = 0; i < pages.length; ++i) {
String page = pages[i];
String baseUrl = getBaseUrl(page);
for (var link : externalLinks[i]) {
if (ps.containsKey(link)) {
int linkIndex = ps.get(link);
linkScores[linkIndex] += (double) basicScores[i] / externalLinks[i].size();
}
}
}- 외부 링크된 각 페이지에 현재 페이지의 링크 점수를 계산하기 위해 먼저 해당 웹 페이지 url과 인덱스 번호를 저장한다. 특정 인덱스에 대한 외부 링크 번호를 저장하는 것도 동일한 방식으로 파싱할 수 있다.
String getBaseUrl(String page) {
String find = "<meta property=\"og:url\" content=\"";
int st = page.indexOf(find) + find.length();
int en = page.indexOf("\"", st);
return page.substring(st, en);
}
List<String> getExternalLinks(String page) {
List<String> links = new ArrayList<>();
int pos = page.indexOf("<a href=\"");
while (pos != -1) {
int start = pos + "<a href=\"".length();
int end = page.indexOf("\"", start);
links.add(page.substring(start, end));
pos = page.indexOf("<a href=\"", end);
}
return links;
}- 기본 점수를 구하기 위해 각 페이지 Body부분에 word가 몇 번 반복되었는지 계산한다.
int getBasicScore(String word, String page) {
String lowerPage = page.toLowerCase();
String body = lowerPage.substring(lowerPage.indexOf("<body>") + 7, lowerPage.indexOf("</body>"));
int score = 0;
String[] words = body.split("[^a-zA-Z]");
for (var w : words) {
if (w.equals(word)) {
score++;
}
}
return score;
}- 기본 점수와 링크 점수를 합한 뒤 매칭 점수가 더 크다면 인덱스를 갱신하는 방식으로 답을 구한다.
double[] totalScores = new double[pages.length];
for (int i = 0; i < pages.length; ++i) {
totalScores[i] = basicScores[i] + linkScores[i];
}
int ans = 0;
for (int i = 1; i < pages.length; ++i) {
if (totalScores[i] > totalScores[ans]) {
ans = i;
}
}
return ans;개선
시간복잡도
- n = 페이지 수, L = 페이지 길이, K = 외부 링크 수
코드
import java.util.*;
class Solution {
public int solution(String word, String[] pages) {
word = word.toLowerCase();
Map<String, Integer> ps = new HashMap<>(); // url, index
List<String>[] externalLinks = new ArrayList[pages.length];
int[] basicScores = new int[pages.length];
double[] linkScores = new double[pages.length];
for (int i = 0; i < pages.length; ++i) {
externalLinks[i] = new ArrayList<>();
String baseUrl = getBaseUrl(pages[i]);
ps.put(baseUrl, i);
basicScores[i] = getBasicScore(word, pages[i]);
externalLinks[i] = getExternalLinks(pages[i]);
}
for (int i = 0; i < pages.length; ++i) {
String page = pages[i];
String baseUrl = getBaseUrl(page);
for (var link : externalLinks[i]) {
if (ps.containsKey(link)) {
int linkIndex = ps.get(link);
linkScores[linkIndex] += (double) basicScores[i] / externalLinks[i].size();
}
}
}
double[] totalScores = new double[pages.length];
for (int i = 0; i < pages.length; ++i) {
totalScores[i] = basicScores[i] + linkScores[i];
}
int ans = 0;
for (int i = 1; i < pages.length; ++i) {
if (totalScores[i] > totalScores[ans]) {
ans = i;
}
}
return ans;
}
String getBaseUrl(String page) {
String find = "<meta property=\"og:url\" content=\"";
int st = page.indexOf(find) + find.length();
int en = page.indexOf("\"", st);
return page.substring(st, en);
}
int getBasicScore(String word, String page) {
String lowerPage = page.toLowerCase();
String body = lowerPage.substring(lowerPage.indexOf("<body>") + 7, lowerPage.indexOf("</body>"));
int score = 0;
String[] words = body.split("[^a-zA-Z]");
for (var w : words) {
if (w.equals(word)) {
score++;
}
}
return score;
}
List<String> getExternalLinks(String page) {
List<String> links = new ArrayList<>();
int pos = page.indexOf("<a href=\"");
while (pos != -1) {
int start = pos + "<a href=\"".length();
int end = page.indexOf("\"", start);
links.add(page.substring(start, end));
pos = page.indexOf("<a href=\"", end);
}
return links;
}
}
꾸준하게