매칭 점수
프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
- 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
- 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
- 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
- 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
예를 들어, 다음과 같이 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> 태그의 값으로 주어진다.
- 예를들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은 https://careers.kakao.com/index 이다.
- <meta property="og:url" content="https://careers.kakao.com/index" />
- 한 웹페이지에서 모든 외부 링크는 <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을 리턴하면 된다.
-----------------------------
정규표현식 사용
import re # 정규표현식
from collections import defaultdict # 키가 초기화 안돼 있어도 삽입 시 기본값으로 설정. 오류안남
def solution(word, pages):
answer = []
# 단어 소문자
word = word.lower()
# 기본점수, 외부링크수
database = defaultdict(list) # list로 defaultdict 설정
# 어떤 외부 링크가 참조되었는지 저장
ext_link = defaultdict(list)
for page in pages:
# url 추출
# <meta property="og:url" content="https://careers.kakao.com/interview/list"/>
# [1.] meta 분리
# [<meta property="og:url" content="https://careers.kakao.com/interview/list"]
meta = re.findall("<meta property=[\"]og:url.*[\"]", page)[0] # list형식이므로 0을 반환
# [2.] content의 url 추출
# content="https://careers.kakao.com/interview/list"
content = re.findall("content=.*[\"]", meta)[0].replace("content=", '') # content의 URL
body = re.findall("<body>.*</body>", page, re.DOTALL)[0] # DOTALL : \n 까지 포함
# 외부링크
external_links = re.findall('<a href\S*"', body) # 외부 링크
# 외부링크수
ext_cnt = len(external_links)
base_score = 0
texts = re.findall("[a-zA-Z]+", page) #단어별로 구분
# 기본점수
for text in texts:
if text.lower() == word:
base_score += 1
for i in range(ext_cnt):
external_links[i] = external_links[i].replace("<a href=", "") # 불필요한 부분 삭제
ext_link[external_links[i]].append(content) # 외부링크의 데이터에 현재 content를 추가
# 점수 저장. [기본점수, 외부링크수]
database[content][0:2] = [base_score, ext_cnt]
for data in database:
base_score, ext_cnt = database[data]
ext_score = 0
for ext in ext_link[data]:
a, b = database[ext]
ext_score += (a / b)
match_score = base_score + ext_score
answer.append(match_score)
return answer.index(max(answer))'공부 > 알고리즘' 카테고리의 다른 글
| [프로그래머스] 길 찾기 게임 / 2019 카카오 블라인드 채용 / python (0) | 2021.05.23 |
|---|---|
| [프로그래머스] 블록 게임 / 2019 카카오 블라인드 채용 / python (0) | 2021.05.23 |
| BFS (0) | 2021.04.09 |
댓글