[JAVA] 프로그래머스 LEVEL3 매칭 점수 (정규 표현식 문제)

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

프로그래머스

코딩테스트 연습 > 2019 KAKAO BLIND RECRUITMENT > 매칭 점수

 

난이도: LEVEL3

알고리즘 유형: 정규 표현식 + 구현 

문제 풀이 

이번 문제는 정규 표현식을 활용하는 문제였다. 

 

해당 HTML에서 HOME URL: 해당 웹사이트의 url을 찾는 방법

String regex1 = "<meta property=\"og:url\" content=\"https://.*?\"";
String regex2 = "<a href=\"https://.*?\">";

Pattern pattern1 = Pattern.compile(regex1);
Pattern pattern2 = Pattern.compile(regex2);

public static String findHomeUrl(String page, Pattern pattern1, Pattern pattern2){
    Matcher matcher1 = pattern1.matcher(page);  
    if(matcher1.find()){
        Matcher matcher2 = pattern2.matcher(matcher1.group());
        if(matcher2.find()){
            return matcher2.group();
        }
    }
    return "";
}

 

먼저 regex1에 해당하는 패턴을 찾는다.

처음부터 regex2에 해당하는 패턴을 찾으면 외부 링크 또한 같이 나오기 때문에 해당 방식을 사용했다.

 

Greedy vs non-Greedy 

regex1에서 .*/" 이렇게 해도 값은 똑같이 나오지만 

.*?/" 이렇게 하는게 더 성능상 훨씬 좋다 

 

이는 탐색 방식이 달라서 그렇다. 

.*/"는 그리디 탐색이다 /" 큰따옴표가 나와도 문자열 끝까지 다 찾은 이후에 첫 큰 따옴표 앞까지 반환

.?/"는 non 그리디 탐색이다. /" 큰따옴표가 나오면 바로 탐색을 멈춘다. 

 

만약 문자열의 길이가 1억이면 .*/"는 문자열 끝까지 탐색한다. 

 

외부링크 찾기 

String regex2 = "<a href=\"https://.*?\">";
String regex3 = "https://[^\"]+";

Pattern pattern2 = Pattern.compile(regex2);
Pattern pattern3 = Pattern.compile(regex3);

public static ArrayList<String> findLink(String page, Pattern pattern1, Pattern pattern2){
    ArrayList<String> list = new ArrayList<>();
    Matcher matcher1 = pattern1.matcher(page);
    while(matcher1.find()){
        Matcher matcher2 = pattern2.matcher(matcher1.group());
        if(matcher2.find()){
            list.add(matcher2.group());
        }
    }
    return list;
}

 

단어를 포함 개수 찾기 

String regex4 = "(?<=[^A-Za-z])" + word + "(?=[^A-Za-z])";

// 대소문자 상관없이 매칭 = Pattern.CASE_INSENSITIVE
Pattern pattern4 = Pattern.compile(regex4, Pattern.CASE_INSENSITIVE);

public static int findWordMatch(String page, Pattern pattern){
    int cnt = 0;
    Matcher matcher = pattern.matcher(page);
    while(matcher.find()){
        cnt++;
    }
    return cnt;
}

 

pages 순회하면서 데이터를 Site로 가공하여 map에 저장

static class Site {
    int index; // index 
    Double score; // 기본 점수 
    ArrayList<String> links; // 외부 링크 목록 
    Double offer_score; // score / links.size()
    Double match_score; // 기본 점수 + 외부 점수 
    Site(int index, double score, ArrayList<String> links){
        this.index = index;
        this.score = score;
        this.links = links;
        this.offer_score = score / links.size();
        this.match_score = score;
    }
}

static Map<String, Site> map = new HashMap<>(); 

for(int i = 0; i < pages.length; i++){
    String url = findHomeUrl(pages[i], pattern1, pattern3);
    ArrayList<String> links = findLink(pages[i], pattern2, pattern3);
    int score = findWordMatch(pages[i], pattern4);
    Site site = new Site(i, Double.valueOf(score), links);
    map.put(url, site);
}

 

매칭 점수에 링크 점수 더해주기 

ArrayList<Site> list = new ArrayList<>(map.values());

for(Site cur : list){
    for(String url : cur.links){
        if(map.containsKey(url))
        map.get(url).match_score += cur.offer_score;
    }
}

 

정렬

list.sort((o1, o2) -> {
    int result = o1.match_score.compareTo(o2.match_score);
    if(result != 0) return -result; // 매칭 점수가 큰 순서대로 
    return o1.index - o2.index; // index가 작은 순서대로 
});

 

매칭 점수가 큰 순서대로 만약 같다면 index가 작은 순서대로 정렬한다.

 

정답 반환

return list.get(0).index;

정답 코드 

import java.util.*;
import java.util.regex.*;
class Solution {
    static class Site {
        int index; // index 
        Double score; // 기본 점수 
        ArrayList<String> links; // 외부 링크 목록 
        Double offer_score; // score / links.size()
        Double match_score; // 기본 점수 + 외부 점수 
        Site(int index, double score, ArrayList<String> links){
            this.index = index;
            this.score = score;
            this.links = links;
            this.offer_score = score / links.size();
            this.match_score = score;
        }
    }
    static Map<String, Site> map = new HashMap<>(); 
    public int solution(String word, String[] pages) {
        // non-greedy 매칭 .*? 
        String regex1 = "<meta property=\"og:url\" content=\"https://.*?\"";
        String regex2 = "<a href=\"https://.*?\">";
        String regex3 = "https://[^\"]+";
        // 후방탐색 + 전방탐색 
        String regex4 = "(?<=[^A-Za-z])" + word + "(?=[^A-Za-z])";
        Pattern pattern1 = Pattern.compile(regex1);
        Pattern pattern2 = Pattern.compile(regex2);
        Pattern pattern3 = Pattern.compile(regex3);
        // 대소문자 상관없이 매칭 = Pattern.CASE_INSENSITIVE
        Pattern pattern4 = Pattern.compile(regex4, Pattern.CASE_INSENSITIVE);
        
        for(int i = 0; i < pages.length; i++){
            String url = findHomeUrl(pages[i], pattern1, pattern3);
            ArrayList<String> links = findLink(pages[i], pattern2, pattern3);
            int score = findWordMatch(pages[i], pattern4);
            Site site = new Site(i, Double.valueOf(score), links);
            map.put(url, site);
        }
        ArrayList<Site> list = new ArrayList<>(map.values());
        
        // 매칭 점수 (링크 점수 더하기)
        for(Site cur : list){
            for(String url : cur.links){
                if(map.containsKey(url))
                map.get(url).match_score += cur.offer_score;
            }
        }
        
        list.sort((o1, o2) -> {
            int result = o1.match_score.compareTo(o2.match_score);
            if(result != 0) return -result; // 매칭 점수가 큰 순서대로 
            return o1.index - o2.index; // index가 작은 순서대로 
        });
        
        return list.get(0).index;
    }
    // 기본점수 구하기 
    public static int findWordMatch(String page, Pattern pattern){
        int cnt = 0;
        Matcher matcher = pattern.matcher(page);
        while(matcher.find()){
            cnt++;
        }
        return cnt;
    }
    // 외부링크 찾는 메소드 
    public static ArrayList<String> findLink(String page, Pattern pattern1, Pattern pattern2){
        ArrayList<String> list = new ArrayList<>();
        Matcher matcher1 = pattern1.matcher(page);
        while(matcher1.find()){
            Matcher matcher2 = pattern2.matcher(matcher1.group());
            if(matcher2.find()){
                list.add(matcher2.group());
            }
        }
        return list;
    }
    // HomeUrl 찾는 메소드 
    public static String findHomeUrl(String page, Pattern pattern1, Pattern pattern2){
        Matcher matcher1 = pattern1.matcher(page);  
        if(matcher1.find()){
            Matcher matcher2 = pattern2.matcher(matcher1.group());
            if(matcher2.find()){
                return matcher2.group();
            }
        }
        return "";
    }
}