공부/Algorithm

[Programmers] [Level3] 매칭 점수

mariabeetle 2020. 9. 10. 13:52

https://programmers.co.kr/learn/courses/30/lessons/42893

 

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

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

programmers.co.kr

풀이

  • 특정 단어 word, html 소스로 구성된 pages를 입력으로 받음.
  • 각 page별로 word에 대한 점수를 부여해야 하는데 다음 과정으로 구함.
    • 본문(body tag)에서 word의 개수를 기본 점수로 정함.
      • 본문은 알파벳을 제외한 다른 문자로 구별가능하고, 대소문자 상관 없이 word와 딱 맞아야함.
        • word = 'abc', body에 'abcd', 'abcabc'는 매칭되지 않음, 'abc', 'AbC'가 되어야 매칭
    • 다른 웹페이지에서 외부 링크(a tag에 있는 웹주소)를 통해 접속되는 경우 링크 점수를 계산해 더해줌.
      • b라는 웹페이지에 a, c페이지로 갈 수 있는 외부 링크가 있음.
      • b에는 word가 4번 등장(기본 점수 4), 외부 링크 개수는 2.
      • a페이지, c페이지는 링크 점수로 2점이 추가됨(기본 점수 / 외부 링크 개수)
    • 점수 = 기본 점수 + 링크 점수
  • 링크 점수가 가장 높은 page의 index를 반환. 점수가 같다면 먼저 등장한 page의 index 반환
  • 문제 자체는 어렵지 않은데, 파싱을 잘 못하면 오답 발생. Test case로는 정보가 매우 부족하고 여러 태그가 어떤 형식으로 나올지 몰라서 푸는데 시간이 오래 걸림
  • 처음에는 정규표현식으로만 문자열을 골라내려했는데 실패 -> split으로 직관적으로 문자열을 나눔
  • base_score_dict에는 page의 주소를 key값으로, word의 출현 빈도를 value로 한 dictionary
  • link_score_dict에는 page의 외부 링크를 key값으로, 기본 점수를 더할 때 링크 점수를 더해주게 됨.
  • 마지막에 총 점수 구해서 sort, index구해줌.
def solution(word, pages):
    import re
    from collections import defaultdict
    # 기본 점수 저장
    base_score_dict = {}
    # 링크 점수 저장. (기본 점수 구할 때 외부 링크에 링크 점수를 더해나감)
    link_score_dict = defaultdict(int)
    # body tag 안에 a tag 파싱하기 위한 정규표현식
    a_parser = re.compile('a href="(.+)*"')

    for idx, page in enumerate(pages):
        page_url = page.split('<meta property=\"og:url\" content=\"')[1].split('\"')[0]
        body_text = page.split('<body>')[1].split('</body>')[0]
        # 외부 링크 저장
        a_hrefs = []
        for link_long in page.split('<a href=\"')[1:]:
            a_hrefs.append(link_long.split('">')[0])

        # body tag안의 모든 문자열을 lower로 바꾸고, 알파벳이 아니면 '.'으로 바꿈. 
        # 그리고 '.'에 대해 split해서 list 만듬.
        body_text = re.sub('[^a-z]+', '.', body_text.lower()).split('.') 
        # word를 소문자로 바꾼 뒤, 위에서 만든 리스트와 매칭되는 개수 count -> 기본 점수
        base_score = len(list(filter(lambda x:x==word.lower(), body_text)))
        # 기본 점수 저장할 때 idx도 같이 저장.
        base_score_dict[page_url] = (base_score, idx)

        # 각각의 외부링크마다 링크 점수를 더해줌.
        for a_href in a_hrefs:
            link_score_dict[a_href] += (base_score/len(a_hrefs)) 

    score = []
    for key, values in base_score_dict.items():
        base_score = values[0]
        idx = values[1]
        link_score = link_score_dict[key]
        score.append((idx, base_score + link_score))

    return sorted(score, key=lambda x:(x[1], -x[0]), reverse=True)[0][0]
저작자표시