문제
프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
- 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
- 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
- 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
- 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
예를 들어, 다음과 같이 A, B, C 세 개의 웹페이지가 있고, 검색어가 hi라고 하자.
이때 A 웹페이지의 매칭점수는 다음과 같이 계산할 수 있다.
- 기본 점수는 각 웹페이지에서 hi가 등장한 횟수이다.
- A,B,C 웹페이지의 기본점수는 각각 1점, 4점, 9점이다.
- 외부 링크수는 다른 웹페이지로 링크가 걸린 개수이다.
- A,B,C 웹페이지의 외부 링크 수는 각각 1점, 2점, 3점이다.
- A 웹페이지로 링크가 걸린 페이지는 B와 C가 있다.
- A 웹페이지의 링크점수는 B의 링크점수 2점(4 ÷ 2)과 C의 링크점수 3점(9 ÷ 3)을 더한 5점이 된다.
- 그러므로, A 웹페이지의 매칭점수는 기본점수 1점 + 링크점수 5점 = 6점이 된다.
검색어 word와 웹페이지의 HTML 목록인 pages가 주어졌을 때, 매칭점수가 가장 높은 웹페이지의 index를 구하라. 만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 구하라.
[제한사항]
- pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고, 길이는 1 이상 20 이하이다.
- 한 웹페이지 문자열의 길이는 1 이상 1,500 이하이다.
- 웹페이지의 index는 pages 배열의 index와 같으며 0부터 시작한다.
- 한 웹페이지의 url은 HTML의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.
- 예를들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은 https://careers.kakao.com/index 이다.
- <meta property="og:url" content="https://careers.kakao.com/index" />
- 한 웹페이지에서 모든 외부 링크는 <a href="https://careers.kakao.com/index"\>의 형태를 가진다.
- <a> 내에 다른 attribute가 주어지는 경우는 없으며 항상 href로 연결할 사이트의 url만 포함된다.
- 위의 경우에서 해당 웹페이지는 https://careers.kakao.com/index 로 외부링크를 가지고 있다고 볼 수 있다.
- 모든 url은 https:// 로만 시작한다.
- 검색어 word는 하나의 영어 단어로만 주어지며 알파벳 소문자와 대문자로만 이루어져 있다.
- word의 길이는 1 이상 12 이하이다.
- 검색어를 찾을 때, 대소문자 구분은 무시하고 찾는다.
- 예를들어 검색어가 blind일 때, HTML 내에 Blind라는 단어가 있거나, BLIND라는 단어가 있으면 두 경우 모두 해당된다.
- 검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영한다.
- 단어는 알파벳을 제외한 다른 모든 문자로 구분한다.
- 예를들어 검색어가 "aba" 일 때, "abab abababa"는 단어 단위로 일치하는게 없으니, 기본 점수는 0점이 된다.
- 만약 검색어가 "aba" 라면, "aba@aba aba"는 단어 단위로 세개가 일치하므로, 기본 점수는 3점이다.
- 결과를 돌려줄때, 동일한 매칭점수를 가진 웹페이지가 여러 개라면 그중 index 번호가 가장 작은 것를 리턴한다
- 즉, 웹페이지가 세개이고, 각각 매칭점수가 3,1,3 이라면 제일 적은 index 번호인 0을 리턴하면 된다.
풀이
먼저 문제에서 필요한 것을 정리하면,
해당 페이지의 주소 : <meta property="og:url" content="url"/> 형식에서 url이 필요
기본 점수 : 검색어 등장 횟수
외부링크수 : <a herf="url"/> 식의 태그 존재 갯수
링크점수 : 연결된 링크들의 기본점수 / 외부링크수 총합
매칭점수 : 기본점수 + 링크점수
이렇게 다섯가지의 정보가 필요하다.
우선
String linkPattern = "<meta property=\"og:url\" content=\"https://\\S*\"/>";
Pattern.matches(linkPattern, tag[index].trim())위의 정규식 코드를 이용하여 페이지의 주소가 있는 태그를 찾았다.
static String findPage(String tag){
String result = "";
String[] content = tag.trim().split("\\s");
result = content[2].substring(9, content[2].length() - 3);
return result;
}찾은 태그에서 url 을 위의 메소드를 이용해서 분리해 주었다. 해당페이지의 주소를 저장한다.
이렇게 분리하 url 을 HashMap 에 넣어 index를 저장했다.(나중에 링크점수를 계산하기 위해)
아래 정규식을 이용해서 <body> </body> 태그 안에 존재하는 링크를 저장했다.
static String url_Pattern = "<a href=\"\\S*\">";
static Pattern urlPattern = Pattern.compile(url_Pattern);
while(index < tag.length && !tag[index].equals("</body>")){
Matcher urlMatcher = urlPattern.matcher(tag[index]);
//링크 개수 파악 및 링크 추가
while(urlMatcher.find()){
linkList.add(urlMatcher.group().split("\"")[1]);
}
}이렇게 찾아진 링크를 urlMatcher.group().split("\"") 를하면 찾아진 <a href="" /> 태그에서 " 를 기준으로 나눠준 String 에서 첫번째가 url 이 있는 위치가 된다. 이렇게 외부링크수를 저장한다.
이렇게 url 을 분리하여 list 에 추가해준다.
단어는 MuziMuzi 의 경우 Muzi와 일치하지 않지만 Muzi@Msuzi 면 2개 일치하기 때문에 알파벳이 아닌 것들로 잘라준 뒤 단어씩 비교하였다. 기본점수를 계산하였다.
//단어별로 잘라서 단어 일치하는지 확인 -> 기본점수
String[] tags = tag[index].toLowerCase().split("[^a-z]");
for(int j = 0 ; j < tags.length ; j++){
if(tags[j].equals(word.toLowerCase())){
count++;
}
}
해당 링크가 연결된 페이지에 현재 페이지의 (기본점수/외부링크수) 를 저장하여 링크점수를 더해준다.
for(int i = 0 ; i < pages.length ; i++){
double score = (double)webs[i].basicScore / (double)webs[i].linkCount;
for(String link : webs[i].linkList){
if(map.containsKey(link)){
int index = map.get(link);
webs[index].linkScore += score;
}
}
}
링크점수가 저장되면 매칭점수를 알 수 있으므로 매칭점수를 계산한 뒤 최대값을 찾아주면 된다.
<전체코드>
import java.util.*;
import java.util.regex.*;
class Solution {
static class webInfo{
int basicScore;
int linkCount;
double linkScore;
double matchingScore;
List<String> linkList;
webInfo(int basic, int linkCount, List<String> linkList){
this.basicScore = basic;
this.linkCount = linkCount;
this.linkList = linkList;
}
public void setMatchScore(){
this.matchingScore = this.basicScore + this.linkScore;
}
}
static String url_Pattern = "<a href=\"\\S*\">";
static Pattern urlPattern = Pattern.compile(url_Pattern);
public int solution(String word, String[] pages) {
int answer = 0;
webInfo[] webs = new webInfo[pages.length];
HashMap<String, Integer> map = new HashMap<String, Integer>();
for(int i = 0 ; i < pages.length ; i++){
String[] tag = pages[i].split("\n");
int index = 0;
String linkPattern = "<meta property=\"og:url\" content=\"https://\\S*\"/>";
while(index < tag.length && !Pattern.matches(linkPattern, tag[index].trim())){
index++;
}
String link = findPage(tag[index]);
map.put(link, i);
while(index < tag.length && !tag[index].equals("<body>")){
index++;
}
index++;
List<String> linkList = new ArrayList<String>();
int count = 0;
while(index < tag.length && !tag[index].equals("</body>")){
Matcher urlMatcher = urlPattern.matcher(tag[index]);
//링크 개수 파악 및 링크 추가
while(urlMatcher.find()){
linkList.add(urlMatcher.group().split("\"")[1]);
}
//단어별로 잘라서 단어 일치하는지 확인 -> 기본점수
String[] tags = tag[index].toLowerCase().split("[^a-z]");
for(int j = 0 ; j < tags.length ; j++){
if(tags[j].equals(word.toLowerCase())){
count++;
}
}
index++;
}
webs[i] = new webInfo(count, linkList.size(), linkList);
}
for(int i = 0 ; i < pages.length ; i++){
double score = (double)webs[i].basicScore / (double)webs[i].linkCount;
for(String link : webs[i].linkList){
if(map.containsKey(link)){
int index = map.get(link);
webs[index].linkScore += score;
}
}
}
double max = 0;
for(int i = 0 ; i < pages.length ; i++){
webs[i].setMatchScore();
if(max < webs[i].matchingScore){
max = webs[i].matchingScore;
answer = i;
}
}
return answer;
}
static String findPage(String tag){
String result = "";
String[] content = tag.trim().split("\\s");
result = content[2].substring(9, content[2].length() - 3);
return result;
}
}
이문제가 String 분석의 끝판왕 수준의 문제였다. 정규식도 많이 활용하여 더욱 쉽고 짧게 문제를 풀 수 있다. 아직 정규식 활용에 부족하다는 것을 느꼈다.
'자료구조 공부 > String' 카테고리의 다른 글
| [프로그래머스] 순위검색 (0) | 2021.05.26 |
|---|---|
| [프로그래머스] 광고삽입** (0) | 2021.05.25 |
| [프로그래머스] 셔틀버스 (0) | 2021.05.23 |
| [프로그래머스] 추석트래픽 (0) | 2021.05.17 |
| [프로그래머스] 불량사용자 (0) | 2021.05.11 |