-
[프로그래머스] 매칭 점수 (2019 KAKAO BLIND RECRUITMENT)ALGORITHM/PROGRAMMERS 2021. 3. 29. 21:38
programmers.co.kr/learn/courses/30/lessons/42893
코딩테스트 연습 - 매칭 점수
매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀
programmers.co.kr
2021-03-29
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115import java.util.*;import java.util.regex.Matcher;import java.util.regex.Pattern;public class Solution42893 {static class Link {int index;int base;int out;double linked;public Link(int index, int base, int out, double linked) {this.index = index;this.base = base;this.out = out;this.linked = linked;}}public static String extractBody(String word) { // body 추출Pattern bodyPt = Pattern.compile("<body>(?s)(.*)</body>"); // <body>와 </body> 태그 사이에 있는 문장 추출Matcher bodyMat = bodyPt.matcher(word);String body = "";if (bodyMat.find()) {body = bodyMat.group(1);}return body;}public static int solution(String word, String[] pages) {int answer = 987654321;word = word.toLowerCase();HashMap<String, Link> map = new HashMap<>();String[] names = new String[pages.length];for (int i = 0; i < pages.length; i++) {// url 추출Pattern urlPt = Pattern.compile("<meta property=\"og:url\" content=\"https://(\\S*)\""); // url extractMatcher urlMat = urlPt.matcher(pages[i]);String url = "";if (urlMat.find()) {url = urlMat.group(1);}// body 부분 추출String body = extractBody(pages[i]);// 외부 링크 수 countPattern aPt = Pattern.compile("<a href="); // <a href= 개수Matcher aMat = aPt.matcher(body);int aCnt = 0;while (aMat.find()) {aCnt++;}// 검색어 등장 횟수body = body.toLowerCase();int srchCnt = 0;int index = 0;while (true) {index = body.indexOf(word, index + 1);if (index < 0) break;char prev = body.charAt(index - 1);char post = body.charAt(index + word.length());if (!Character.isLetter(prev) && !Character.isLetter(post)) { // 양쪽 모두 글자가 아니어야함srchCnt++;}}map.put(url, new Link(i, srchCnt, aCnt, 0.0));names[i] = url;}for (int i = 0; i < pages.length; i++) {String body = extractBody(pages[i]);// 링크 점수Pattern aPt = Pattern.compile("<a href=\"https://(\\S*)\""); // <a href= 링크 개수Matcher aMat = aPt.matcher(body);String aUrl = "";while (aMat.find()) {aUrl = aMat.group(1);Link origin = map.get(names[i]);if (map.get(aUrl) != null && origin.base != 0 && origin.out != 0) {double link = (double) origin.base / (double) origin.out;Link tmp = map.get(aUrl);tmp.linked += link;map.put(aUrl, tmp);}}}//큰 매칭 값 찾기Iterator<String> keys = map.keySet().iterator();double value = 0.0;while (keys.hasNext()) {String next = keys.next();double matching = map.get(next).base + map.get(next).linked;if (value <= matching) {if (value == matching) answer = Math.min(answer, map.get(next).index);else answer = map.get(next).index;value = matching;}}return answer;}public static void main(String[] args) {// String w = "blind";// String[] p = {"<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@blINd 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>\nSuspendisblINdse potenti. Vivamus venenatis tellus non turpis bibendum, \neiei<a href=\"https://a.com\"> Link to a Blind </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>"};String w = "Muzi";String[] p = {"<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>#!0muzi0muzi0!)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>"};System.out.println(solution(w, p));}}cs #문제풀이
생각보다 되게 오래 걸렸었던 문제이다. 그만큼 코드도 깔끔하지는 못하다,,,
1. line 38 ~ : url 추출하는 패턴을 사용했다. 맨처음 key값이 될 수 있는 url을 추출하였다. <meta ~ 로 시작하여 content 안에 있는 글자를 추출하였다.
2. line 45 ~ + extractBody() : body 부분을 추출했다. <body>와 </body> 사이를 추출했다. 나중에 한 번 더 사용하려고 따로 빼서 사용했다.
3. line 47 ~ : 외부 링크 수를 count 했다. 단순히 <a href=로 시작하는 것의 개수를 세었다. (외부 링크 수 : 현재 페이지에서 외부로 연결된 링크 수)
4. line 54 ~ : lowercase로 바꾼 후 검색어 등장 횟수를 체크했다. 찾고자 하는 word의 index를 찾은 후 그 word index의 앞과 word index + word.length의 뒤를 살펴 보았을 때 둘 다 글자가 아닌 경우 완벽하게 한 단어로 추출 할 수 있는 것이므로, 이 조건을 만족한 경우 수를 세주었다. (기본점수 : 찾고자 하는 글자 수)
5. 위에 1~4번을 이용해서 url key 값을 뽑아내었고, 기본점수, 외부 링크 수를 계산하여 value값에 넣었다.
6. line 70 ~ : body를 다시 한 번 추출해서, <a href=의 링크를 뽑아내었다. 위에서 key 값을 모두 뽑아내었으므로, 뽑아낸 링크가 key값에 존재하는 경우 그리고 기본 점수와 외부 링크 수가 0이 아닌 경우 링크 점수를 계산해주고 map에 추가해주었다. (링크 점수 : 다른 웹 페이지에서 해당 웹페이지로 외부 링크가 걸렸을 때, 그 다른 웹페이지의 기본점수 / 외부 링크 수)
7. line 89~ : 만들어놓은 map을 돌면서 매칭 점수(기본 점수 + 링크 점수)를 계산 해주었다. index 값을 애초에 들고 다녔으므로 그냥 단순하게 index 값도 매칭점수 값 비교할 때 함께 비교했다.
'ALGORITHM > PROGRAMMERS' 카테고리의 다른 글
[프로그래머스] 카카오프렌즈 컬러링북 (2017 카카오코드 예선) (0) 2021.06.27 [프로그래머스] 네트워크 (0) 2021.04.15 [프로그래머스] 수식 최대화 (2020 카카오 인턴십) (0) 2021.03.15 [프로그래머스] 튜플 (2019 카카오 개발자 겨울 인턴십) (0) 2021.03.07 [프로그래머스] 오픈채팅방 (2019 KAKAO BLIND RECRUITMENT) (0) 2021.03.05