공부기록
매칭점수 본문
- 문제 설명
매칭 점수
프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
- 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
- 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
- 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
- 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
예를 들어, 다음과 같이 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을 리턴하면 된다.
입출력 예 #1
- word : blind
- pages :
- ["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://a.com\"/>\n</head> \n<body>\nBlind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. \n<a href=\"https://b.com\"> Link to b </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://b.com\"/>\n</head> \n<body>\nSuspendisse potenti. Vivamus venenatis tellus non turpis bibendum, \n<a href=\"https://a.com\"> Link to a </a>\nblind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.\n<a href=\"https://c.com\"> Link to c </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://c.com\"/>\n</head> \n<body>\nUt condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind\n<a href=\"https://a.com\"> Link to a </a>\n</body>\n</html>"]
- pages는 다음과 같이 3개의 웹페이지에 해당하는 HTML 문자열이 순서대로 들어있다.
Blind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. Link to b
Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum, Link to a blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut. Link to c
Ut condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind Link to a
위의 예를 가지고 각각의 점수를 계산해보자.
- 기본점수 및 외부 링크수는 아래와 같다.
- a.com의 기본점수는 3, 외부 링크 수는 1개
- b.com의 기본점수는 1, 외부 링크 수는 2개
- c.com의 기본점수는 1, 외부 링크 수는 1개
- 링크점수는 아래와 같다.
- a.com의 링크점수는 b.com으로부터 0.5점, c.com으로부터 1점
- b.com의 링크점수는 a.com으로부터 3점
- c.com의 링크점수는 b.com으로부터 0.5점
- 각 웹 페이지의 매칭 점수는 다음과 같다.
- a.com : 4.5 점
- b.com : 4 점
- c.com : 1.5 점
따라서 매칭점수가 제일 높은 첫번째 웹 페이지의 index인 0을 리턴 하면 된다.
입출력 예 #2
- word : Muzi
- pages :
- ["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://careers.kakao.com/interview/list\"/>\n</head> \n<body>\n<a href=\"https://programmers.co.kr/learn/courses/4673\"></a>#!MuziMuzi!)jayg07con&&\n\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://www.kakaocorp.com\"/>\n</head> \n<body>\ncon%\tmuzI92apeach&2<a href=\"https://hashcode.co.kr/tos\"></a>\n\n\t^\n</body>\n</html>"]
- pages는 다음과 같이 2개의 웹페이지에 해당하는 HTML 문자열이 순서대로 들어있다.
#!MuziMuzi!)jayg07con&&
con% muzI92apeach&2 ^
- 기본점수 및 외부 링크수는 아래와 같다.
- careers.kakao.com/interview/list 의 기본점수는 0, 외부 링크 수는 1개
- www.kakaocorp.com 의 기본점수는 1, 외부 링크 수는 1개
- 링크점수는 아래와 같다.
- careers.kakao.com/interview/list 의 링크점수는 0점
- www.kakaocorp.com 의 링크점수는 0점
- 각 웹 페이지의 매칭 점수는 다음과 같다.
- careers.kakao.com/interview/list : 0점
- www.kakaocorp.com : 1 점
따라서 매칭점수가 제일 높은 두번째 웹 페이지의 index인 1을 리턴 하면 된다.
- 내 코드
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
class Solution {
public int solution(String word, String[] pages) {
int answer = 0;
double basic_score[] = new double[pages.length];
double total_score[] = new double[pages.length];
for(int i=0; i<pages.length; i++){
basic_score[i] = 0; total_score[i] = 0;
}
HashMap<String, Integer> addr_to_idx = new HashMap<>();
Vector<String> outer_link[] = new Vector[pages.length];
for(int i=0; i<outer_link.length; i++)
outer_link[i] = new Vector<String>();
Vector<Integer> outer_idx[] = new Vector[pages.length];
for(int i=0; i<outer_idx.length; i++)
outer_idx[i] = new Vector<Integer>();
String pages_split[][] = new String[pages.length][];
for(int i=0; i<pages.length; i++)
pages_split[i] = pages[i].split("\n");
//현재 주소, 외부 주소, 기본 점수
for(int i=0; i<pages.length; i++){
String cur_str = pages[i];
String tmp_str;
//1. 자기 주소 가져가기
tmp_str = cur_str.split("<head>")[1].split("</head>")[0];
Pattern my_pat = Pattern.compile("<meta property=\"og:url\" content=\"(\\S+)\"\\/>");
Matcher my_mat = my_pat.matcher(tmp_str);
while(my_mat.find()){
String tmp_addr = my_mat.group();
tmp_addr = tmp_addr.trim().split(" ")[2];
int s_idx = tmp_addr.indexOf("https");
int e_idx = tmp_addr.lastIndexOf("\"/>");
addr_to_idx.put(tmp_addr.substring(s_idx, e_idx), i);
}
//2. 외부 주소 가져가기
tmp_str = cur_str;
my_pat = Pattern.compile("<a href=\"(\\S+)\"");
my_mat = my_pat.matcher(tmp_str);
while(my_mat.find()){
String tmp_addr = my_mat.group();
int s_idx = tmp_addr.indexOf("https");
int e_idx = tmp_addr.lastIndexOf("\"");
outer_link[i].add(tmp_addr.substring(s_idx, e_idx));
}
//3. 단어 수집
tmp_str = cur_str.toLowerCase().replaceAll("[^a-z]", " ");
my_pat = Pattern.compile("\\b"+word.toLowerCase()+"\\b");
my_mat = my_pat.matcher(tmp_str);
double count = 0;
while(my_mat.find()){
count++;
}
basic_score[i] = count;
}
for(int i=0; i<pages.length; i++){
for(String link : outer_link[i]){
if(addr_to_idx.get(link) != null){
outer_idx[i].add(addr_to_idx.get(link));
}
}
}
for(int i=0; i<pages.length; i++){
double cur_score = (double)basic_score[i]/(double)outer_link[i].size();
for(int next_idx : outer_idx[i]){
total_score[next_idx] += cur_score;
}
}
double max_val = -1;
for(int i=0; i<pages.length; i++){
total_score[i] += basic_score[i];
if(total_score[i] > max_val){
answer = i;
max_val = total_score[i];
}
}
return answer;
}
}
- 피드백
- 일단 완벽하게 푸는데 4시간 이상 소요되었다.... 못풀었다고 봐야함
- 먼저 정규식을 제대로 몰라 푸는데 많은 시간이 소요... 프로그래머스에 정규식 관련 공짜 강의가 있으니 시간내서 들어야 될 필요가 있다.
- 정규식 관련해서 저 "\\b" + word + "\\b"의 경우 처음에 기존의 문서에서 숫자를 변환해주지 않고 "[^a-b]" + word + "[^a-b"]해도 되지 않아서 확인해보니 커서가 넘어가 0word0word0word0에서 가운데가 인식되지 않는 문제가 있었다... 그래서 일단 숫자를 공백으로 바꿔주어 글자의 경계를 만들어주니 통과... 추후에 숫자로 바꾸는 부분을 [^a-b]로 바꾸어 영문자가 아닌 모든 문자를 공백으로 바꾸어주어도 통과했다.
- 파씽에도 문제가 있었다 특히 head안의 meta tag를 조건으로 명시했는데 지키지 않아 35점만 맞다가 다시 조건에 철저하도록 수정하니 95점까지 올라감... 제약조건을 항상 잘 보도록하자. 실제로 나머지 파싱은 딱히 제약조건이 없어 전체에서 그대로 했는데 그냥 맞음...
- 점수를 double로 안하면 8번 테케에서 틀린다. 근데 5점만 나가서 실제 테스트였다면 큰 이슈는 아니었을 것.
- 큰 설계는 어렵지 않았지만 정규식을 어설프게 쓰다보니 제대로 풀지 못했다... 정규식을 시간내서 공부하자.
'코테/프로그래머스' Related Articles
more
