Programmers. 매칭 점수

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 매칭 점수

문제 풀이

처음 문제를 봤을 땐 대체 뭐 이리 더럽나 싶었는데 정규식으로 얼마나 깔끔하게 파싱할 수 있는지 묻는 문제였다.

먼저 단어는 대소문자 구분이 없으므로 전부 소문자로 만들어 준다. 그리고 각 페이지의 점수 계산을 위해 단어가 포함된 개수와 외부 링크 수를 저장할 hash 구조, 자신에게 링크를 보내오는 url을 저장할 hash 구조, 좌표를 기준으로 어떤 url을 갖는 페이지인지 저장할 hash구조 총 3개의 hash 구조를 정의해야 한다.

먼저 각 페이지에 대해 역시나 전부 소문자로 만들어두고 정규표현식을 사용해 url을 ㅜ출한다.

• 정규표현식 : r'<meta[^>]*content="http://(\S+)"/>'

괄호는 search 시 매칭되는 요소를 저장하며 \S는 공백 등을 제외한 문자를 의미한다.

페이지에 보함된 단어를 세야하는데 [a-z]+이면 알파벳이 1개 이상 반복되는 모든 문자를 의미하므로 공백, 특수문자를 모두 거를 수 있다. 조회된 모든 단어들에 대해 word와 비교하여 일치하면 카운트를 1 올린다.

단어 카운트를 구했으므로 해당 페이지의 점수를 기록할 hash 구조에 현재 url을 키로 찾아 삽입한다. 외부 url은 중복을 염두해 우선 set을 선언한 뒤 정규식에 매칭되는 전체 결과들에 대해 카운트하고 그 길이를 역시 점수 hash 구조에 현재 url을 키로 삽입한다. 이로써 링크 점수가 결정되었다.

외부 링크 입장에선 현재 url이 연결을 보내왔으므로 링크를 보내는 url을 저장할 hash 구조에 각 원소를 key값으로 삼아 현재 url을 삽입한다.

모든 페이지에 대해 순회가 끝나면 페이지 좌표를 기준으로 url을 찾고 해당 url의 기본 점수를 계산하고 외부로부터 들어온 모든 url에 대해 링크 점수를 계산하여 더한 뒤 최댓값인지 갱신한다.

• 좌표에서 url로 변환할 hash, 현재 url의 단어 매칭과 외부 링크를 저장할 hash, 자신에게 링크를 건 링크들을 저장할 hash 선언
• word와 각 페이지들을 소문자로 변환
• 정규식 r'<meta[^>]*content="https://(\S*)"/>'을 사용, url 추출
• 단어 r'[a-z]+를 사용, 모든 단어 추출하여 비교, 카운트
• 외부 링크 r'<a href="https://(\S*)"> 사용하여 모든 외부연결 url 추출, 개수를 저장하고 각 링크에 대해 외부접속링크 목록에 현재 url 추가
• 페이지를 모두 순회하여 점수 계산, 최댓값 갱신

python 코드

import re
from collections import defaultdict
def solution(word, pages):
    answer = 0
    word = word.lower()
    url_to_idx = defaultdict(list)
    url_score = defaultdict(list)
    url_from_link = defaultdict(list)
    for i in range(len(pages)):
        page = pages[i].lower()
        url = re.search(r'<meta[^>]*content="https://(\S*)"/>', page).group(1)
        word_cnt = 0
        for find in re.findall(r'[a-z]+', page):
            if find == word:
                word_cnt += 1
        url_score[url].append(word_cnt)
        url_to_idx[i] = url
        wordCnt = 0
        exLinkSet = set()
        for e in re.findall(r'<a href="https://(\S*)">', page):
            exLinkSet.add(e)
        url_score[url].append(len(exLinkSet))
        for e in exLinkSet:
            url_from_link[e].append(url)
    ans_score = 0
    anser = 0
    for i in range(len(pages)):
        url = url_to_idx[i]
        basic_score = url_score[url][0]
        link_score = 0
        for e in url_from_link[url]:
            link_score += url_score[e][0] / url_score[e][1]
        score = basic_score + link_score
        if score > ans_score:
            ans_score = score
            answer = i
    return answer