티스토리 뷰
[프로그래머스/자바] 매칭 점수 풀이 - 2019 KAKAO BLIND RECRUITMENT
hrniin 2022. 12. 10. 00:56https://school.programmers.co.kr/learn/courses/30/lessons/42893
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
2019 KAKAO BLIND RECRUITMENT Level 3 문제다.
입력으로 들어온 웹페이지의 매칭 점수를 각 구하고,
매칭 점수가 들어있는 list를 정렬해 list의 가장 앞에 있는 페이지의 인덱스를 반환하면 된다.
이를 구현하기 위해 먼저 Page class를 만든다.
클래스에는 url, score(기본 점수), idx, outlink_cnt(외부 링크 수), match(매칭 점수), outlink(외부 링크가 담긴 배열)의 변수가 존재한다.
매칭 점수는 기본 점수와 링크 점수의 합이므로, 매칭 점수를 기본 점수로 초기화한다.
그 다음 해당 페이지로 링크가 걸린 페이지들이 있다면 매칭 점수에 링크 점수를 누적합 해주면 된다.
이 변수들을 초기화해줄
입력으로 들어온 웹페이지의 url, 기본 점수, 외부 링크를 구해 Page 객체를 생성하고 생성한 Page 객체를 ArrayList에 넣는다.
1) 웹페이지의 url (findUrl() method)
웹페이지 자신의 url은 <meta property="og:url" content="로 시작해서 "로 끝난다.
즉, indexOf를 통해 <meta property=\"og:url\" content=\"의 위치 start를 찾고,
<meta property=\"og:url\" content=\" 다음에 나오는 "의 위치 end를 찾는다.
substring으로 start + delim.length() 부터 end까지 자르면 url이 된다.
url은 <meta~를 포함하지 않고 그 다음부터이므로 length()를 더해준다.
2) 기본 점수
<body>와 </body> 사이를 substring을 통해 추출한다.
이때 대소문자 구분이 없으므로 str와 word 모두 toLowerCase()를 통해 소문자로 바꿔준다.
영어를 제외한 모든 문자로 단어를 구분하므로 replaceAll("[^a-z]", " "); 로 소문자 알파벳이 아닌 문자는 빈칸으로 교체한다.
그리고 StringTokenizer를 통해 빈칸을 기준으로 단어를 잘라준다.
st.nextToken()으로 word와 같은지 비교하고, 같다면 기본점수 score를 1 더해준다.
* 이때 <body>안에 있는 <a> ~ </a>를 모두 삭제한 후 단어를 세어주었더니 테스트 케이스 10을 틀렸었다.
외부 링크에는 word와 같은 단어가 들어오지 않는 건가?
테케 10번 때문에 엄청 시간을 많이 소비함..
3) 외부 링크
외부 링크는 <a href="로 시작해서 "로 끝난다.
url과 유사한 방식으로 링크만 추출해서 ArrayList에 넣어주면 된다.
외부 링크가 여러개인 경우가 있으므로 str에 <a href="가 포함될 때까지 while문을 반복한다.
while문이 무한루프가 되지 않도록 외부 링크 하나를 찾을 때마다 그 외부 링크 이후의 문자열로 str를 잘라준다,
외부 링크가 담긴 ArrayList를 String[]으로 바꿔 반환한다.
입력으로 들어온 페이지 모두 list에 넣었다면,
list의 외부 링크를 모두 탐색해 링크 점수를 계산한다.
만약 a라는 페이지가 b를 참조했다면, a 페이지의 outlink에 b가 저장되어 있지만 b의 링크 점수가 증가해야 한다.
즉, 모든 페이지의 outlink를 꺼내면서 그 outlink과 동일한 url을 찾아야 한다.
이중for문으로 list의 url과 outlink를 돌면서 링크 점수를 계산했다.
그리고 list를 매칭 점수, 인덱스 별로 정렬한다.
매칭 점수가 높은 순서대로, 매칭 점수가 같다면 인덱스가 낮은 순서대로 람다식을 작성했다.
정렬된 list의 가장 첫번째 페이지의 인덱스를 반환하면 된다.
배운점 및 느낀점
정규표현식을 잘 알지 못해서 String의 substring과 indexOf 위주로 문제를 풀었다.
확실히 정규표현식으로 푼 코드들이 깔끔하고 길이도 짧은 것 같아서 이번 기회에 제대로 배워봐야겠다.
그리고 [^a-z]처럼 특정 문자를 제외하고자 할 때 사용하는 정규표현식은 항상 헷갈려서
사용할 때마다 구글링으로 찾아보곤 했는데, 이번 기회에 확실히 알게 되었다.
코드에 사용하진 않았지만 Character.isLetter() 함수도 어떤 기능인지 알았다.
나한텐 Level 3 문제치고는 너무 어렵게 느껴져서 문자열 처리에 대해 더 많이 공부해야겠다고 생각했다..!
import java.util.*;
class Solution {
public int solution(String word, String[] pages) {
ArrayList<Page> list = new ArrayList<>();
word = word.toLowerCase();
for(int i=0;i<pages.length;i++) {
String page = pages[i];
String url = findUrl(page);
if(url.equals(""))
continue;
int score = findWord(page, word);
String[] outlink = findOutlink(page);
Page p = new Page(i, url, score, outlink);
list.add(p);
}
// 링크점수 계산하기
for(int i=0;i<list.size();i++) {
Page out = list.get(i);
for(String link : out.outlink) {
for(int j=0;j<list.size();j++) {
Page in = list.get(j);
if(j != i && in.url.equals(link))
in.addLinkScore(out.score / (double)out.outlink_cnt);
}
}
}
// 1. 매칭 점수 내림차순 2. 인덱스 오름차순 정렬
list.sort((o1, o2) -> Double.compare(o1.match, o2.match) == 0 ? o1.idx - o2.idx :
Double.compare(o2.match, o1.match));
return list.get(0).idx;
}
static String findUrl(String str) {
String delim = "<meta property=\"og:url\" content=\"";
int start = str.indexOf(delim) + delim.length();
int end = str.indexOf("\"", start);
return str.substring(start, end);
}
static int findWord(String str, String word) {
// body 부분만 추출
str = str.substring(str.indexOf("<body>"), str.indexOf("</body>"));
// 알파벳을 제외한 모든 문자는 빈칸으로 교체
str = str.toLowerCase().replaceAll("[^a-z]", " ");
StringTokenizer st = new StringTokenizer(str);
int score = 0;
// 단어 단위로 자르기
while(st.hasMoreTokens()) {
if(st.nextToken().equals(word))
score++;
}
return score;
}
static String[] findOutlink(String str) {
String delim_s = "<a href=\"";
String delim_e = "\">";
ArrayList<String> list = new ArrayList<>();
int start = 0; int end = 0;
while(str.contains(delim_s)) {
start = str.indexOf(delim_s) + delim_s.length();
end = str.indexOf(delim_e, start);
String link = str.substring(start, end);
list.add(link);
str = str.substring(end);
}
return list.toArray(new String[0]);
}
static class Page {
String url;
int score, idx, outlink_cnt;
double match = 0;
String[] outlink;
Page(int idx, String url, int score, String[] outlink) {
this.idx = idx;
this.url = url;
this.score = score; // 기본 점수
this.match = score; // 매칭 점수의 default는 기본 점수
this.outlink = outlink; // 외부 링크가 담긴 배열
this.outlink_cnt = outlink.length; // 외부 링크 갯수
}
void addLinkScore(double link) {
this.match += link;
}
}
}'algorithm > programmers' 카테고리의 다른 글
| [프로그래머스/자바] 방금그곡 풀이 - 2018 KAKAO BLIND RECRUITMENT (0) | 2022.12.29 |
|---|---|
| [프로그래머스/자바] 길 찾기 게임 풀이 - 2019 KAKAO BLIND RECRUITMENT (0) | 2022.12.16 |
| [프로그래머스/자바] 압축 풀이 - 2018 KAKAO BLIND RECRUITMENT (0) | 2022.12.02 |
| [프로그래머스/자바] 파일명 정렬 풀이 - 2018 KAKAO BLIND RECRUITMENT (0) | 2022.12.01 |
| [프로그래머스/자바] n진수 게임 - 2018 KAKAO BLIND RECRUITMENT (0) | 2022.12.01 |