[프로그래머스] 🔍 매칭 점수 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT

[프로그래머스] 🔍 매칭 점수 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT

문제 설명

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

한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.

한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)

한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.

한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.

한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.

예를 들어, 다음과 같이 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의 태그 내에 태그의 값으로 주어진다.

• 예를들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은 https://careers.kakao.com/index 이다.

• 한 웹페이지에서 모든 외부 링크는 의 형태를 가진다.

• 내에 다른 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을 리턴하면 된다.

😃 나의 코드

import re

def solution(word, pages):
    answer = 0
    meta_parser = re.compile('<meta(.+?)/>')
    a_parser = re.compile('<a(.+?)>')
    page_infos = []
    for page in pages:
        page_dict = dict()
        a_tags = a_parser.findall(page)
        outer_url = []
        for a_tag in a_tags:
            first_idx = end_idx = -1
            for idx, char in enumerate(a_tag):
                if char == '"':
                    if first_idx == -1:
                        first_idx = idx
                    elif end_idx == -1:
                        end_idx = idx
            outer_url.append(a_tag[first_idx+1:end_idx])
        meta_tag = meta_parser.search(page).group()
        content_prop = meta_tag.split(' ')[2]
        first_idx = end_idx = -1 
        for idx, char in enumerate(content_prop):
            if char == '"':
                if first_idx == -1:
                    first_idx = idx
                elif end_idx == -1:
                    end_idx = idx
        url = content_prop[first_idx+1: end_idx]
        page_dict['outer_url_list'] = outer_url
        page_dict['url'] = url
        page_dict['keyword_point'] = re.sub('[^a-z]+', '.', page.lower()).split('.').count(word.lower())
        page_dict['link_point'] = 0
        page_infos.append(page_dict)
    for page_info in page_infos:
        for outer_url in page_info['outer_url_list']:
            for outer_url_page_candidate in page_infos:
                if outer_url == outer_url_page_candidate['url']:
                    outer_url_page_candidate['link_point'] += page_info['keyword_point']/len(page_info['outer_url_list'])
    point_lst = [page_info['keyword_point'] + page_info['link_point'] for page_info in page_infos]
    print(point_lst)
    return point_lst.index(max(point_lst))

Python의 내장 모듈인 re를 이용해야하는 문제였습니다.

첫 번째 파싱해야 할 것은 키워드입니다. 키워드 파싱에는 re 모듈의 sub를 이용했습니다. re.sub(pattern, repl, string)으로 이루어진 sub는 string에서 pattern과 매치하는 텍스트를 repl로 바꿔주는 역할을 합니다. 문제의 설명에서 단어는 알파벳을 제외한 다른 모든 문자로 구분한다 라는 설명을 이용하여 알파벳 대소문자 이외에 모든 문자들을 . 로 바꿔줍니다. 그 뒤 string의 split('.') 이용하여 알파벳들로 이루어진 단어의 배열을 만들어줍니다 그 뒤 해당 배열에서 단어의 갯수를 세는 count 함수로 마무리합니다. 모든 경우에서 대소문자를 구분하지 않도록 했기 때문에 string의 lower를 모든 string에 추가해줍니다.

두 번째 파싱해야 할 것은 해당 페이지의 url입니다. 정규표현식은 r"<meta(.+?)/>" 로 파싱 결과값은 meta tag 전체입니다. 그 뒤 split과 큰 따옴표의 index를 찾아가는 방식으로 url을 찾아냅니다.

세 번째 파싱해야 할 것은 페이지 안에 있는 외부 링크의 url입니다. 정규 표현식은 r"<a(.+?)>" 로 meta tag의 경우와 비슷합니다.

위의 두 파싱에서 저는 큰 따옴표를 찾아 index를 이용해 string을 잘라내는 방식을 짰는 데, split('\"')를 이용했다면 좀 더 간단하게 짤 수 있습니다.

파싱이 모두 마무리되면 각 정보를 각각의 page별 dictionary 자료형에 넣습니다.

마지막으로 링크 점수를 계산하기 위해 전체 page를 돌면서 링크 점수를 가산하면 풀이가 마무리됩니다.

정규표현식이 아직은 서툴러서 필요한 데이터를 파싱하는 데 좀 오래걸리고, 데이터 사전 조작 부분에서 아예 생각을 하지 못했던 것이 아쉬웠습니다. 이런 파싱류의 작업은 데이터 사전 작업이 중요하다는 것을 알게되었습니다. meta tag와 외부 링크를 찾아내는 방법도 split 함수를 이용하면 좀 더 간단하게 구할 수 있었습니다.