본문 바로가기
Dot Algo∙ DS/PS

[프로그래머스] 2019 카카오 블라인드 #6 매칭 점수 (Java)

루지 2021. 9. 1.

    #6 매칭 점수

    난이도 : LEVEL 3

    유형 : 정규식, 문자열

     

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

    매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀

    programmers.co.kr

    ▸ 문제

    프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
    평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
    그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.

    • 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
    • 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
    • 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
    • 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
    • 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.

    예를 들어, 다음과 같이 A, B, C 세 개의 웹페이지가 있고, 검색어가 hi라고 하자.

     

    이때 A 웹페이지의 매칭점수는 다음과 같이 계산할 수 있다.

    • 기본 점수는 각 웹페이지에서 hi가 등장한 횟수이다.
      • A,B,C 웹페이지의 기본점수는 각각 1점, 4점, 9점이다.
    • 외부 링크수는 다른 웹페이지로 링크가 걸린 개수이다.
      • A,B,C 웹페이지의 외부 링크 수는 각각 1점, 2점, 3점이다.
    • A 웹페이지로 링크가 걸린 페이지는 B와 C가 있다.
      • A 웹페이지의 링크점수는 B의 링크점수 2점(4 ÷ 2)과 C의 링크점수 3점(9 ÷ 3)을 더한 5점이 된다.
    • 그러므로, A 웹페이지의 매칭점수는 기본점수 1점 + 링크점수 5점 = 6점이 된다.

    검색어 word와 웹페이지의 HTML 목록인 pages가 주어졌을 때, 매칭점수가 가장 높은 웹페이지의 index를 구하라. 만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 구하라.

    ▸ 제한사항

    • pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고, 길이는 1 이상 20 이하이다.
    • 한 웹페이지 문자열의 길이는 1 이상 1,500 이하이다.
    • 웹페이지의 index는 pages 배열의 index와 같으며 0부터 시작한다.
    • 한 웹페이지의 url은 HTML의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.
    • 한 웹페이지에서 모든 외부 링크는 <a href="https://careers.kakao.com/index"\>의 형태를 가진다.
      • <a> 내에 다른 attribute가 주어지는 경우는 없으며 항상 href로 연결할 사이트의 url만 포함된다.
      • 위의 경우에서 해당 웹페이지는 https://careers.kakao.com/index 로 외부링크를 가지고 있다고 볼 수 있다.
    • 모든 url은 https:// 로만 시작한다.
    • 검색어 word는 하나의 영어 단어로만 주어지며 알파벳 소문자와 대문자로만 이루어져 있다.
    • word의 길이는 1 이상 12 이하이다.
    • 검색어를 찾을 때, 대소문자 구분은 무시하고 찾는다.
      • 예를들어 검색어가 blind일 때, HTML 내에 Blind라는 단어가 있거나, BLIND라는 단어가 있으면 두 경우 모두 해당된다.
    • 검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영한다.
      • 단어는 알파벳을 제외한 다른 모든 문자로 구분한다.
      • 예를들어 검색어가 "aba" 일 때, "abab abababa"는 단어 단위로 일치하는게 없으니, 기본 점수는 0점이 된다.
      • 만약 검색어가 "aba" 라면, "aba@aba aba"는 단어 단위로 세개가 일치하므로, 기본 점수는 3점이다.
    • 결과를 돌려줄때, 동일한 매칭점수를 가진 웹페이지가 여러 개라면 그중 index 번호가 가장 작은 것를 리턴한다
      • 즉, 웹페이지가 세개이고, 각각 매칭점수가 3,1,3 이라면 제일 적은 index 번호인 0을 리턴하면 된다.

     

    문제 풀이  

    실전에서는 무조건 후순위로 둘 것이다. 간단한 정규식 문자열 문제이면 몰라도 이렇게 안써본 정규식을 구현하는 것은 힘들 것 같다. 그래도 시간만 충분하다면 데이터를 쪼개고 쪼개서 풀 수는 있는 문제이다. 정규식 사용하는 부분은 공부하는 셈치고 풀이를 참고했다.

     

    구상 

    정규식으로 추출해야 할 데이터는 meta태그 안에 있는 해당 페이지 https://주소와 body 태그 안에 외부와 연결되어있는 a태그 안의 주소를 구해주면 된다.

     

    • \S는 공백 문자가 아닌 나머지 문자를 나타낸다.
    • * 앞 문자가 없을 수도 무한정 많을 수도 있음을 나타낸다. (0,~)
    • \b는 단어의 경계를 나타낸다.
    • () 소괄호 안의 문자를 하나의 문자로 인식한다.
    • ? 앞 문자가 없거나 하나 있음을 나타낸다 (0,1)
    • (?i)는 패턴 매칭에 사용되는 플래그로, 대소문자를 구분하지 않는다. 
    Pattern pageUrlPattern = Pattern.compile("<meta property=\"og:url\" content=\"(\\S*)\"");
Pattern outUrlPattern = Pattern.compile("<a href=\"(\\S*)\"");
Pattern wordPattern = Pattern.compile("\\b(?i)"+word+"\\b");
    •  

    이렇게 구한 데이터로 각 페이지당 외부 링크 점수, 기본 점수를 구한 후 외부와 연결된 주소들을 조회하여 추가로 점수를 계산해주면 된다.

    matcher = outUrlPattern.matcher(page); // outUrlPattern에 매치되는 값을 저장한다.
List<String> urlList = new ArrayList<>();
while (matcher.find()) { // 매치된 값이 있으면 true, 없으면 false를 반환한다.
	String out = matcher.group(1); // 매치된 값을 반환한다.
	urlList.add(out);
}

     

    Matches 메소드

    • group() 매칭된 부분을 반환한다.
    • group(int idx) 매칭된 부분 중 idx번 그룹핑 매칭부분을 반환한다
    • 예를 들어 outUrlPattern ("<a href=\"(\\S*)\"") 으로 <a href="https://hashcode.co.kr/tos" 를 찾아냈다고 하면 다음과 같다.

     

    설계

    1. 각 페이지를 순차적으로 탐색하여 각 페이지에 대한 데이터를 구한다.
      1. Map 자료구조로 각 주소에 외부링크들 데이터를 담는다. pageLink.put(home, urlList); 
        1. home : 해당 페이지의 주소를 저장한다. (pageUrlPattern)
        2. urlList : 해당 페이지의 외부 링크들 주소를 List 데이터로 모아 저장한다. (outUrlPattern)
      2. 페이지의 단어의 갯수를 조사하여 기본 점수를 매긴다. (wordPattern)
    2. 1번에서 구한 페이지의 데이터를 종합해 List데이터에 저장한다. new Page(int idx,double out, double total);
      1. out : 한 페이지의 링크 점수로, 기본 점수/ 외부 링크 수이다. (double) basicScore / pageLink.get(home).size()
      2. total : (기본 점수+ 링크 점수)로, 현재까지는 기본 점수만 저장한다.
    3. 각 페이지의 외부링크들을 조회하여 total점수에 외부 링크 점수를 더해준다. outPage.total += posPage.out;
    4. total 점수를 기준으로 오름차순으로 정렬하여 가장 빠른 페이지 index를 출력해준다.

     

    풀이 코드 

    import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map; 
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    public int solution(String word, String[] pages) {
		int numOfPages = pages.length;

		Map<String, Page> pageData = new HashMap<>();
		Map<String, List<String>> pageLink = new HashMap<>();
		Pattern pageUrlPattern = Pattern.compile("<meta property=\"og:url\" content=\"(\\S*)\"");
		Pattern outUrlPattern = Pattern.compile("<a href=\"(\\S*)\"");
		Pattern wordPattern = Pattern.compile("\\b(?i)"+word+"\\b");
		Matcher matcher;
		String home = "";
		String body = "";
		for (int i = 0; i < numOfPages; i++) {
			String page = pages[i];
			matcher = pageUrlPattern.matcher(page);
			if (matcher.find()) {
				home = matcher.group(1);
			}
            
			matcher = outUrlPattern.matcher(page);
			List<String> urlList = new ArrayList<>();
			while (matcher.find()) {
				String out = matcher.group(1);
				urlList.add(out);
			}
			pageLink.put(home, urlList);

			body = page.split("<body>")[1];
			body = body.split("</body>")[0].replaceAll("[0-9]", " ");

			matcher = wordPattern.matcher(body.toLowerCase());
			int basicScore = 0;
			while (matcher.find()) {
				basicScore++;
			}

			pageData.put(home,
					new Page(i, ((double) basicScore / pageLink.get(home).size()), basicScore));
		}

		for (String key : pageLink.keySet()) {
			Page posPage = pageData.get(key);
			for (String out : pageLink.get(key)) {
				if(pageData.containsKey(out)) {
					Page outPage = pageData.get(out);
					outPage.total += posPage.out;
				}
			}
		}

		List<Page> res = new ArrayList<>(pageData.values());
		Collections.sort(res);
		return res.get(0).idx;
	}

	static class Page implements Comparable<Page> {
		int idx;
		double out;
		double total;

		public Page(int idx,double out, double total) {
			this.idx = idx;
			this.out = out;
			this.total = total;
		}

		@Override
		public int compareTo(Page o) {
			double a = o.total-this.total;
			if(a==0) {
				return Integer.compare(this.idx, o.idx);
			}else {
				return Double.compare(o.total, this.total);	
			}
		}
	}
}

    'Dot Algo∙ DS > PS' 카테고리의 다른 글

    [BOJ] 백준 4256번 트리 (Java)  (0) 2021.09.02
    [프로그래머스] 2019 카카오 블라인드 #7 블록 게임 (Java)  (0) 2021.09.01
    [프로그래머스] 2019 카카오 블라인드 #5 길 찾기 게임 (Java)  (0) 2021.09.01
    [프로그래머스] 2019 카카오 블라인드 #4 무지의 먹방 라이브 (Java)  (0) 2021.08.31
    [프로그래머스] 2019 카카오 블라인드 #3 후보키 (Java)  (0) 2021.08.30

    'Dot Algo∙ DS/PS' 관련글

    티스토리툴바

    티스토리툴바