프로그래머스 - 매칭 점수

leehyunjon·2022년 5월 14일

레벨3 정규식 카카오 프로그래머스

Algorithm

목록 보기

30/162

매칭 점수 : https://programmers.co.kr/learn/courses/30/lessons/42893#

Problem

Solve

문제자체는 어렵지 않지만 정규식을 모르면 하드코딩을 해야하는 문제.

문자열에서 특정 패턴의 문자열을 찾기위해 util.Pattern 라이브러리를 사용하였다.

사용한 Pattern, Matcher 함수

Pattern.complie() : 정규식을 통해 찾고자하는 문자열 패턴 설정
[패턴 인스턴스].matcher("문자열") : 전체 문자열을 argument로 넣고 패턴에 맞는 문자열 정보를 Matcher 클래스로 반환받는다.
[매처 인스턴스].find() : 패턴이 일치하는 문자열이 있다면 true를 반환한다.
[매처 인스턴스].group() : 패턴과 동일한 문자열을 문자열로 반환한다.

사용한 정규식

\ \S : whitespace를 제외한 문자
\ \b : 단어의 공백

문제 풀이순서는 아래와 같다.

Pattern과 Matcher를 통해 웹페이지 url과 외부 링크 url 그리고 word의 갯수를 통해 기본점수를 구한다.
- Map<String, Integer>를 통해 url과 index를 매칭시킨다.
- List[] 를 통해 각 index에 url(웹 페이지 url, index,외부 링크, 기본점수)정보를 저장한다.
List에 저장된 url를 돌면서 외부 링크에 현재 웹페이지의 링크점수를 더해준다.
각 url에 저장된 링크점수에 자신의 기본점수를 저장한다.
최종 링크점수를 기준으로 내림차순 정렬한다.
리스트의 처음 URL의 index를 반환한다.

Code

import java.util.regex.*;
import java.util.*;
class Solution {
    HashMap<String,Integer> urlMap;
    URL[] urls;
    public int solution(String word, String[] pages) {
        urlMap = new HashMap<>();
		urls = new URL[pages.length];

		word = word.toLowerCase();
		for(int i=0;i<pages.length;i++){
			pages[i] = pages[i].toLowerCase();
		}

		for(int i=0;i<pages.length;i++){
        	//웹페이지 url 패턴(content= 이후의 url은 띄어쓰기가 없는 문자열을 가지게 되므로 \\S+)
			Pattern urlPattern = Pattern.compile("<meta property=\"og:url\" content=\\S+/>");
            //외부 링크 url 패턴(마찬가지로 href= 이후의 url은 띄어쓰기가 없는 문자열을 가진다)
			Pattern refUrlPattern = Pattern.compile("<a href=\\S+>");
            //body안의 문자열을 분리한 뒤 word를 가지는 패턴(문자가 서로 붙어있다면 같은 word로 판단하지 않겠다는 조건이 있었음)
			Pattern bodyPattern = Pattern.compile("\\b"+word+"\\b");
			Matcher urlMatcher = urlPattern.matcher(pages[i]);
			Matcher refUrlMatcher = refUrlPattern.matcher(pages[i]);
            //숫자를 띄어쓰기로 변경함으로써 숫자로 붙어있는 word를 구분해주기 위함
			Matcher bodyMatcher = bodyPattern.matcher(pages[i].split("<body>")[1].split("</body>")[0].replaceAll("[0-9]", " "));

			int score = 0;
			List<String> refUrlList = new ArrayList<>();
			//웹 페이지 url을 찾았다면 map에 url과 index저장
            if(urlMatcher.find()){
				String url = urlMatcher.group().split("=")[2].split("/>")[0];
				urlMap.put(url, i);
			}

			//매칭된 외부 링크를 모두 list에 저장
			while(refUrlMatcher.find()){
				String url = refUrlMatcher.group().split(">")[0].split("=")[1];;
				refUrlList.add(url);
			}

			//매칭된 word 개수 카운트
			while(bodyMatcher.find()){
				score++;
			}

			//해당 웹페이지 정보 저장
			urls[i] = new URL(i, score, refUrlList);
		}

		//각 URL의 linkscore 계산
		for(URL u : urls){
			double s = u.score;
			int refCount = u.refList.size();
			for(String ref : u.refList){
				if(urlMap.containsKey(ref)){
					urls[urlMap.get(ref)].linkScore += s/refCount;
				}
			}
		}

		//최종 linkscore 갱신
		for(URL u : urls){
			u.setLinkScore();
		}

		//linkscore기준으로 내림차순
		Arrays.sort(urls);

		//가장 높은 linkscore의 url의 index를 반환한다.
		int answer = urls[0].index;
		return answer;
    }
    
    class URL implements Comparable<URL> {
		int index;
		double score;
		double linkScore;
		List<String> refList;
		public URL(int index, int score, List<String> refList){
			this.index = index;
			this.score = score;
			this.refList = refList;
			this.linkScore=0;
		}

		@Override
		public int compareTo(URL o){
			if(o.linkScore > this.linkScore) return 1;
			else if(o.linkScore == this.linkScore) return 0;
			else return -1;
		}

		public void setLinkScore(){
			this.linkScore+=this.score;
		}
	}
}