https://school.programmers.co.kr/learn/courses/30/lessons/42893
[프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/42893)
문제
매칭 점수
프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
- 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
- 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
- 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
- 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
예를 들어, 다음과 같이 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를 구하라. 만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 구하라.
문제 풀이
정규식
문제를 푸는 방법 자체를 생각해내는 것은 어렵지 않았다.
웹페이지 정보를 갖는 클래스를 만들어서 각 웹페이지의 기본점수와 외부링크 정보를 저장하고 계산하기만 하면 된다.
문제는 입력 문자열이 html문이기 때문에 어떻게 이걸 해석해내느냐였다.
<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>하나의 웹페이지가 이런 문자열로 들어온다.
웹페이지의 주소와, body 안에서 외부 링크 주소를 얻어내는 것이 중요하기 때문에 정규식을 이용해서 주소를 얻어냈다.
Pattern urlPattern = Pattern.compile("<meta property=\"og:url\" content=\"https://(\\S*)\"/>");
Pattern outLinkPattern = Pattern.compile("<a href=\"https://(\\S*)\">");보통 모든 문자를 의미하는 정규식으로 .\* 를 사용했는데 통과가 되지 않아서 (//S\*) 를 사용했더니 테스트코드가 통과됐다.
/s는 regex에서 non space를 표현하며 공백 문자가 아닌 것을 의미한다. 그렇기 때문에 영어를 제외한 문자를 모두 걸러내야하는 정규식을 만들 때 좀더 맞는 표현식이었다.
Matcher
Matcher를 활용해 본적이 많이 없었기 때문에 이번에 새롭게 안 Method들이 많았다.
.group() 함수는 정규식을 사용했을 때 포함되는 문자열을 보여주는 함수이다.urlMatcher.group() 실행 시 <meta property="og:url" content="https://a.com"/> 가 반환된다.
하지만 실행 시 아래와 같은 에러메시지가 떴는데,
No match found
java.lang.IllegalStateException: No match found
at java.base/java.util.regex.Matcher.group(Matcher.java:644)
at java.base/java.util.regex.Matcher.group(Matcher.java:603)자세히 알아보니 group()을 실행하기 전에 find()를 한번 실행해서 확인해야한다고 한다.
그래서 실행 부분을 아래처럼 바꾸어 주었다.
while (urlMatcher.find()) {
url = getUrl(urlMatcher.group());
}Double형과 Float형
이전에도 비슷한 이유로 테스트케이스가 통과되지 않은적이 있었는데,
소숫점 연산이 필요할 때 float형을 사용하는 경우이다.
문제에서 링크점수 계산을 위해 소수점 저장 형식으로 float을 사용했었다.
하지만 과정에는 문제가 없음에도 계속 에러가 났고,
다른 풀이를 참고해보니 double형을 사용하고 있길래 혹시나했더니 통과됐다.
앞으로 소수점 사용할 때는 자료형을 Double로 설정해야한다는 점을 기억해두어야 할 것 같다.
전체 코드
import java.util.ArrayList;
import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class s42893 {
private HashMap<String, Page> maps;
private Pattern urlPattern = Pattern.compile("<meta property=\"og:url\" content=\"https://(\\S*)\"/>");
private Pattern outLinkPattern = Pattern.compile("<a href=\"https://(\\S*)\">");
public int solution(String word, String[] pages) {
word = word.toLowerCase();
maps = new HashMap<>();
for (int i = 0; i < pages.length; i++) {
Page now = reorganizeString(pages[i], i, word);
double outScore = now.basicScore / now.outLinks.size();
for (String outLink : now.outLinks) {
if (outLink.equals(now.url)) {
continue;
}
if (!maps.containsKey(outLink)) {
maps.put(outLink, new Page(-1, outLink, 0, new ArrayList<>(), 0));
}
maps.get(outLink).outScore += outScore;
}
}
double[] scores = new double[maps.size()];
int answer = 0;
double maxScore = 0;
for (Page page : maps.values()) {
if (page.index == -1) {
continue;
}
scores[page.index] = page.basicScore + page.outScore;
}
for (int i = 0; i < scores.length; i++) {
if (maxScore < scores[i]) {
maxScore = scores[i];
answer = i;
}
}
return answer;
}
private Page reorganizeString(String page, int index, String word) {
int basicScore = getBasicScore(page, word);
Matcher urlMatcher = urlPattern.matcher(page);
String url = "";
while (urlMatcher.find()) {
url = getUrl(urlMatcher.group());
}
Matcher outLineMatcher = outLinkPattern.matcher(page);
ArrayList<String> outLinks = new ArrayList<>();
while (outLineMatcher.find()) {
String outLink = getOutLink(outLineMatcher.group());
outLinks.add(outLink);
}
if (maps.containsKey(url)) {
maps.get(url).index = index;
maps.get(url).basicScore = basicScore;
maps.get(url).outLinks = outLinks;
} else {
maps.put(url, new Page(index, url, basicScore, outLinks, 0));
}
return maps.get(url);
}
private String getUrl(String metaString) {
return metaString
.replaceAll("<meta property=\"og:url\" content=\"", "")
.replaceAll("\"/>", "");
}
private static String getOutLink(String hrefString) {
return hrefString
.replaceAll("<a href=\"", "")
.replaceAll("\">", "");
}
private int getBasicScore(String page, String word) {
int count = 0;
String body = page
.split("<body>")[1]
.split("</body>")[0]
.toLowerCase();
body = body.replaceAll("<a href=\"https://(\\S*)\">", " ");
body = body.replaceAll("</a>", " ");
for (int i = 0; i < body.length(); i++) {
if (body.charAt(i) > 96 && body.charAt(i) < 123) {
continue;
}
body = body.replace(body.charAt(i), ' ');
}
String[] words = body.split(" ");
for (String now : words) {
if (now.equals(word)) {//완전히 일치
count++;
}
}
return count;
}
private class Page {
int index;
String url;
double basicScore;
ArrayList<String> outLinks;
double outScore;
public Page(int index, String url, double basicScore, ArrayList<String> outLinks,
double outScore) {
this.index = index;
this.url = url;
this.basicScore = basicScore;
this.outLinks = outLinks;
this.outScore = outScore;
}
}
}'코딩테스트' 카테고리의 다른 글
| [백준 7662번] 이중 우선순위 큐 (0) | 2022.01.12 |
|---|---|
| [백준 1718번] 암호 (0) | 2022.01.12 |
| [백준 9489번] 2xn 타일링 (0) | 2022.01.12 |
| [백준 20365번] 2xn 타일링 (0) | 2022.01.11 |
| [백준 1668번] 트로피 진열 (0) | 2022.01.11 |
