개발조아

[프로그래머스] 매칭 점수 파이썬 본문

알고리즘/프로그래머스

[프로그래머스] 매칭 점수 파이썬

개발조아 2021. 12. 1. 22:32
728x90

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42893

 

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

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

programmers.co.kr

 

HTML 파서나 정규식 안쓰고 문자열 처리로 했다.

정규식으로하면 더 쉽게 할 수 있을 것 같긴하다.

 

일일이 문자열을 검색해서 했기 때문에 설명도 길고 코드도 길어졌다.

근데 코드에 어려운부분이 없어서 코드를 보는게 이해가 빠를수도 있다.

 

우선 모든 문자를 소문자로 바꾸고 했다.

html도 word도 모두 대소문자를 구별하지 않기 때문이다.

 

우선 딕셔너리로 page 정보를 저장했다.

'index' : 해당 페이지 인덱스

'count' : 해당 페이지에 단어가 나온 횟수

'links' : 해당 페이지의 외부 링크 배열

'score' : 해당 페이지의 매칭 점수

 

1. 현재 페이지 url 빼기

우선 전체 페이지에서 <meta property="og:url" content=" 이 문자열의 시작 인덱스를 찾는다..

다음 해당위치 다음에서 meta를 닫는 "/> 문자열의 시작 인덱스를 찾는다. 이때 따옴표는 content="의 닫는 따옴표이다.

그럼 두 인덱스 사이의 문자열이 url 이다.

 

2. word 개수 세기

정규식을 이용하면 편할듯하지만 쓸줄 몰라서 그냥 문자열 처리로 했다.

단어는 오직 알파벳이어야 만하고 그외의 문자로 단어들을 구분한다.

그래서 a@a는 a가 두번인 문자열이다.

ab는 ab 한단어이지 a,b 두개의 단어로 치지 않는다.

그래서 word를 찾고 앞,뒤 문자 하나씩 보고 알파벳인지 확인하면 된다.

 

단어가 더이상 없을 때 까지 반복문을 수행한다.

일단 시작은 전체페이지에서 수행한다.

그래서 해당 페이지 문자열에서 단어를 찾는다.

만약 단어가 없다면 반복문을 끝내자.

      나는 index 대신 find로 수행했다.

      index는 없으면 예외처리되고 find는 -1이 리턴된다.

      index를 쓰려면 try, except로 묶고 해도 된다.

 

단어를 찾았으면 해당 인덱스-1의 문자와 (해당 인덱스+단어 길이)의 인덱스 문자가 알파벳인지 확인하자.

     문자열 : (1aaa2) 단어 :  aaa라면 1과 2를 확인하는 것이다.

그래서 둘다 알파벳이라면 개수를 증가시키자.

이때 인덱스가 0이라며 -1의 인덱스는 볼필요가 없다. 왜냐 없기 때문이다.

 

다음 현제 페이지 정보를 갱신하자.

찾은 단어의 위치부터 끝까지로 갱신하면 된다.

그래서 page[인덱스+단어길이-1]로 page를 갱신하자.

 

3. 외부 링크 찾기

 

page 정보에서 body의 시작부분을 찾고 해당 위치 부터 수행했다.

그냥 page 정보에서 <body>문자열을 찾으면 된다.

 

그리고 반복문을 수행하자.

위에서 구한 body 문자열에서 <a href=" 문자열의 시작 인덱스를 구하고

닫는 태그인 "> 문자열도 찾자

그러면 두 위치 사이의 문자열이 외부 링크가 된다.

이때 외부링크가 현재 페이지의 url이라면 외부링크가 아니므로 그냥 지나가자.

 

그리고 다시 body 문자열을 갱신하자.

닫는 태그의 위치부터 끝까지로 갱신하면 된다.

 

4. 매칭 점수 계산

page 정보를 만들 때 score는 count로 초기화를 했다.

이제 링크 점수만 구해주면 된다.

 

링크 점수는 해당 웹페이지로 링크가 걸린 웹페이지의 기본점수/외부링크 수 이다.

좀 헷갈린다.

현재 페이지를 now, 외부 링크를 link라하자.

now에 여러 link가 있을 것이다.

그래서 link 입장에서 봤을 때 now는 link로 연결된 것이고

now는 link로 연결한 것이다.

 

그래서 외부 링크 쪽 매칭점수에 갱신을 수행해야한다.

왜냐 외부 링크로 링크가 걸린 페이지가 now이기 때문이다.

 

 

 

def solution(word, pages):
    word = word.lower()
    web_info = make_web_info(word, pages)
    score, answer = calc_link_score(web_info)
    return answer


def calc_link_score(web_info):

    for url in web_info:
        now = web_info[url]
        for link in now['links']:
            if link not in web_info:
                continue
            web_info[link]['score'] += now['count'] / len(now['links'])

    link_score = 0
    answer = 0
    for url in web_info:
        score = web_info[url]['score']
        index = web_info[url]['index']
        if link_score < score:
            link_score = score
            answer = index
        elif link_score == score:
            answer = min(answer, index)
    return link_score, answer


def make_web_info(word, pages):
    web_info = {}
    index = 0

    for page in pages:
        url = search_url(page).strip()
        count = search_word(word,page)
        links = search_links(page, url)
        web_info[url] = {
            'index': index,
            'count': count,
            'links': links,
            'score': count
        }
        index += 1
    return web_info


def search_url(page):
    start = page.index('<meta property="og:url" content="') + len('<meta property="og:url" content="')
    end = start + page[start:].index('"/>')
    return page[start:end]


def search_word(word, page):
    count = 0
    page = page.lower()
    while True:
        index = page.find(word)
        if index == -1:
            return count
        if 0 < index:
            if not page[index - 1].isalpha() and not page[index+len(word)].isalpha():
                count += 1
        elif index == 0:
            if not page[index + len(word)].isalpha():
                count += 1
        page = page[index + len(word)-1:]


def search_links(page, url):
    body = page[page.index('<body>'):].lower()
    links = []
    try:
        while True:
            start = body.index('<a href="') + len('<a href="')
            end = start + body[start:].index('">')
            link = body[start:end].strip()
            if link != url:
                links.append(link)
            body = body[end + 3:]
    except:
        pass

    return links

'알고리즘 > 프로그래머스' 카테고리의 다른 글

[프로그래머스] 동굴 탐험 파이썬  (0) 2021.12.07
[프로그래머스] 카드 짝 맞추기 파이썬  (0) 2021.12.02
[프로그래머스] 자동완성 파이썬  (0) 2021.11.29
[프로그래머스] 경주로 건설 파이썬  (0) 2021.11.28
[프로그래머스] 보석 쇼핑 파이썬  (0) 2021.11.26
'알고리즘/프로그래머스' Related Articles more
Comments