2019 카카오 신입 공채 1차 - 매칭 점수
* 카카오의 해설은 : 여기
2019 카카오 신입 공채 1차 코딩 테스트 문제 해설
작년에 이어 올해도 블라인드 전형으로 카카오 개발 신입 공채가 시작되었습니다! 그 첫 번째 관문으로 1차 온라인 코딩 테스트가 지난 9월 15일(토) 오후 2시부터 7시까지 5시간 동안 치러졌는데
tech.kakao.com
* programmers 문제 : https://programmers.co.kr/learn/courses/30/lessons/42893
코딩테스트 연습 - 매칭 점수
매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀
programmers.co.kr
programmers level3 정도에 해당하는 문제.
html을 파싱해서 각 페이지 당 점수를 구해 가장 높은 점수를 받은 페이지의 인덱스를 반환하는 문제이다.
구현 문제이고, 문제에서 계산 하라는 대로 따라하면 된다.
카카오 풀이에는 정규식을 사용했지만, 아직 정규식 사용에는 익숙하지 않아서 해당 태그의 index를 find하여 각 정보를 추출해내고, 점수를 계산했다.
크게 html 파일에서 가져와야 할 정보는
- meta tag안의 content url (현재 페이지의 url) => 링크 점수를 구할 때 필요
- body tag안의 a tag (외부 링크 갯수, 외부 링크 주소) => 외부 링크 수
- body tag안의 word 갯수 (이때는 word가 한 단어로만 존재해야 한다. 이것을 체크해주기 위해 앞뒤로 다른 알파벳이 있는지 체크해주었다. isalpha() 함수 사용) => 기본 점수
이렇게 3개를 모두 가져와 dict 에 저장한 다음, 마지막으로 링크점수를 구해주었다. 링크점수는 각 페이지의 content url, 외부 링크 수 를 모두 알고 있어야 하기 때문이다.
각 정보를 가져오는 함수를 만들어서 풀이 했다.
[내 풀이]
# 해당 페이지의 url 찾기
def find_contant(p) :
l_p = len(p)
# <meta property ~ /> 에서 content="
meta_idx = p.find("<meta property")
for i in range(meta_idx, l_p - 1) :
if(p[i] == '/' and p[i + 1] == '>') :
meta = p[meta_idx:i + 2] # <meta property ~ />
c_idx = meta.find('content=')
content = ''
for i in range(c_idx + 9, len(meta)) :
if(meta[i] == '"') :
break
content += meta[i]
return content
# 해당 페이지에서 body 내용 찾기
def find_body(p) :
body_start_idx = p.find("<body>")
body_end_idx = p.find("</body>")
body = p[body_start_idx + 6: body_end_idx]
return body.strip()
# body 안에 <a> tag 찾기
def find_out(body) :
out_urls = []
count = body.count('<a href')
for i in range(count) :
a_start_idx = body.find('<a href="')
out_url = ''
for j in range(a_start_idx + 9, len(body)) :
if(body[j] == '"') :
out_urls.append(out_url)
body = body[:a_start_idx] + body[j + 2:]
break
else :
out_url += body[j]
body = body.replace('</a>', '')
return (out_urls, body.strip().lower())
def find_word(body, word) :
answer = 0
count = body.count(word)
for i in range(count) :
word_idx = body.find(word)
if(word_idx - 1 >= 0 and body[word_idx - 1].isalpha() or word_idx + len(word) < len(body) and body[word_idx + len(word)].isalpha()) :
pass
else :
answer += 1
body = body.replace(word, 'Z', 1) # 어차피 다 소문자이기 때문에 대문자로 치환
return answer
def solution(word, pages):
word = word.lower()
# 각 html의 점수
scores = []
# 각 html의 최종 점수(매칭 점수)
result = []
for p in pages :
# 1. 해당 페이지의 url 찾기
content = find_contant(p)
# 2. 해당 페이지의 body 찾기
body = find_body(p)
# 3. body에서 외부 url 찾기, a태그 제거한 body 받기 -> out score
out_urls, body = find_out(body)
# 4. body에서 word 찾기 -> basic score
basic = find_word(body, word)
# score 저장
scores.append({
'content' : content,
'out_urls' : out_urls,
'out' : len(out_urls),
'basic' : basic,
'link' : 0
})
for i in range(len(scores)) :
url = scores[i]['content']
for j in range(len(scores)) :
if(i == j) :
continue
if(url in scores[j]['out_urls']) :
scores[i]['link'] += scores[j]['basic'] / scores[j]['out']
result.append((i, scores[i]['basic'] + scores[i]['link']))
result = sorted(result, key = lambda x : (-x[1], x[0]))
return result[0][0]
특히 word 갯수를 셀 때, count에 포함된 위치의 word는 다른 알파벳으로 바꾸어 줘야 find할 때 중복으로 체크하지 않는다. (find는 항상 첫번째로 찾은 인덱스를 반환하기 때문에)
태그는 역시 find 를 사용해서 태그의 시작부분을 찾았다.
body 처럼 끝나는 태그가 </body>로 정해져 있다면 <body>, </body>의 인덱스를 찾아 그안의 내용을 가져왔고,
a태그나 meta 처럼 />나 > 로 끝나는 경우에는 for문을 사용해 tag의 끝을 확인해 주었다.
마지막 링크점수는 점수 내림차순 + 인덱스 오름차순 을 key로 정렬하여 맨 처음 요소의 인덱스를 반환했다.
시간은 조금 걸렸지만 풀어서 나름 뿌듯한 문제였다 😊
'알고리즘' 카테고리의 다른 글
| [python]programmers - 메뉴리뉴얼 (0) | 2021.07.21 |
|---|---|
| [python]programmers - 더맵게 (0) | 2021.07.20 |
| [python]재귀 - 하노이의 탑 (0) | 2021.04.24 |
| [python] dijkstra 알고리즘 (0) | 2021.03.22 |
| [python]programmers-소수찾기 (0) | 2021.02.26 |
