2019 Kakao blind - 수식 최대화(정규표현식, 해싱) java 풀이

https://programmers.co.kr/learn/courses/30/lessons/42893

코딩테스트 연습 - 매칭 점수

- 카카오 코테문제들을 풀다보면 정규표현식을 사용할 줄 알면 편리한 문제들이 종종 있다. 물론 substring과 find 등을 이용해서 인덱스 범위를 찾아서 파싱하는 방식으로도 풀 수 있다. 실제 프로젝트에서 접할 수 있는 문제들을 간접적으로 경험할 수 있는 좋은 문제인 것 같다.

- pages의 갯수가 20개, 각 페이지의 문자열의 길이는 1500이므로 별도의 문자열 알고리즘을 사용하지 않고 이중 for문으로 각 페이지마다 필요한 word 매칭 갯수, url 을 추출한다면 1500^2 * 20 = 4500만 연산으로 풀 수 있다.
- 각 페이지마다 url, word 매칭 갯수(=기본점수), 외부 링크를 구해 놓은 다음, 저장 해놓은 페이지를 다시 순회하면서 링크 점수를 구할 수 있다. 이 페이지들을 저장하는 방식은 여러 방법이 있을 수 있는데 본인은 String - Page 페어의 해쉬맵을 1개 만들고 Page class를 정의해서 각 Page의 정보를 저장했다.

- 이 문제를 정규표현식으로 풀기 위해서 자바 regex 패키지와 String 메서드 중 regex를 쓰는 것들을 정리했다. 나중에 따로 포스팅을 할 계획이다. 자바 정규식 패키지를 공부하면서 grouping, backreferences 가 굉장히 편리하는 기능이라는 것을 알게 되었다. 이 문제에서는 grouping을 적극적으로 사용했다.

- 이 문제에서 햇깔리는 부분은 크게 2가지인데, 첫 번째로는 "기본 점수를 구할 때는 단어 단위로 비교해서 완전히 일치하는 경우에만 기본 점수에 반영한다. 그런데 단어는 알파벳을 제외한 다른 모든 문자로 구분한다" 라는 부분이다.
word에 대한 정규식을 \b + word + \b 로 작성하고, 이와 일치하는 부분을 카운트하는 방식으로 접근하였다.
aba - abab 는 일치하지 않지만 aba@ab, aba1a 는 각각 1개가 일치한다. 숫자와 특수문자를 모두 whitespace로 파싱해주고 검색하는 식으로 접근하였다.
\d|\W|_ 로 구현하였는데 d는 0~9 범위의 숫자를 의미하고,W는 alphanumeric([a-zA-Z_0-9]을 제외한 문자를 뜻한다. or 연산으로 합쳤다. 0~9 + 알파벳과 숫자, _를 제외한 문자들 + _ 들이 whitespace가 된다.

- 두 번째로는 링크점수를 구할 때 공식을 구현하는 부분인데, 이 부분은 문제를 정말 정확하게 이해하고 구현했어야 했다.

import java.util.*;
import java.util.regex.*;

class Solution {
    Map<String, Page> map = new HashMap<>();
    
    public int solution(String word, String[] pages) {
        Pattern wordP = Pattern.compile("\\b" + word + "\\b", Pattern.CASE_INSENSITIVE);
        Pattern homeP = Pattern.compile("<meta property=\"og:url\" content=\"https://(\\S*)\"/>");
        Pattern extP = Pattern.compile("<a href=\"https://(\\S*)\">");
        
        for(int i = 0; i < pages.length; ++i) {
            String html = pages[i];
            String homeURL;
            int baseScore;
            List<String> extLink = new ArrayList<>();
            
            Matcher homeMatcher = homeP.matcher(html);
            homeMatcher.find();
            homeURL = homeMatcher.group(1);
            
            String nHtml = html.replaceAll("\\d|\\W|_", " ");
            baseScore = (int)wordP.matcher(nHtml).results().count();
            
            Matcher extMatcher = extP.matcher(html);
            while(extMatcher.find()) {
                extLink.add(extMatcher.group(1));
            }
            
            map.put(homeURL, new Page(homeURL, i, baseScore, extLink));
        }
        
        for(Page page: map.values()) {
            for(String ext: page.extLink) {
                if(map.containsKey(ext)) {
                    Page extPage = map.get(ext);
                    extPage.linkScore += (double)page.baseScore / page.extLink.size();
                }
            }
        }
        
        int maxIdx = -1;
        double maxMatchingScore = -1;
        for(Page page: map.values()) {
            if(maxIdx == -1 || maxMatchingScore < page.getMatchingScore()) {
                maxIdx = page.idx;
                maxMatchingScore = page.getMatchingScore();
            }
        }
        
        return maxIdx;
     }
    
    class Page {
        String homeURL;
        int idx;
        int baseScore;
        List<String> extLink;
        double linkScore;
        
        Page(String homeURL, int idx, int baseScore, List<String> extList) {
            this.homeURL = homeURL;
            this.idx = idx;
            this.baseScore = baseScore;
            this.extLink = new ArrayList<>(extList);
            this.linkScore = 0;
        }
        
        double getMatchingScore() {
            return baseScore + linkScore;
        }
    }
}

https://www.w3schools.com/java/java_regex.asp

Java Regular Expressions

https://docs.oracle.com/javase/9/docs/api/java/util/regex/package-summary.html

java.util.regex (Java SE 9 & JDK 9 )