링크
파일명 정렬 - 2018 카카오 블라인드
난이도
문제 요약
- 페이지의 html정보를 통해 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 계산한다.
- 매칭점수가 가장 높은 페이지의 index를 구하라.
- 기본점수 - 페이지에 word가 매칭되는 갯수
- 외부 링크 수 - 페이지에 외부로 연결되는 링크의 갯수 a태그로 이뤄짐
- 링크 점수 - 자신으로 연결된 모든 페이지의 (기본점수/외부링크 수)의 총합
- 매칭 점수 - (기본점수 + 링크점수)
초반 접근
- 각 페이지마다 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 계산하자
해결법
- 각 페이지 마다 가지는 정보를 한번에 파악 하도록 정리한다.
- map자료구조를 활용
- {자신의주소:[[외부 링크들],기본점수]}
- 기본점수, 외부 링크 수는 html에서 주소영역을 추출하기위해 정규식을 사용
- 기본점수는
<meta property="og:url" content="https://a.com"/>
- 외부링크는
<a href="a.com">
알고리즘 간단 정리
- 페이지 정보 pages, 검색어 word
- 각 page를 순회
- map 자료구조에 {자기주소:[외부링크주소1,…],기본점수}로 key와 value로 저장한다.
- 자기주소는 정규식
/<meta property="og:url" content="(\S+)"\/>/
을 사용
- 외부링크주소는 정규식
/<a href="(\S+)">/g
을 사용 g를 통해 여러개의 결과를 저장
- 기본점수
html.split(/\W|\d/)
를 통해 띄어쓰기 기준으로 단어들을 잘라 word와 같은 갯수 확인
- 링크 점수 계산
- 이중 배열로 page 인덱스를 순회한다.
- 기준 page는 i, 순회하는 page는 j일때
infoI = map.get(기준주소), infoJ = map.get(상대주소)
- i!==j가 아닌 infoJ0가 기준주소를 가지고 있을때
- linkpoint+=(infoJ[1]/infoJ[0].length)
- 매칭점수 계산
후기
- 이 문제는 그저 로직을 정확하게 구현하면 되는 문제이다.
- 하지만 난이도를 위해 복잡한 로직을 추가하고, 문제가 엄청 길어서 독해부터 오래걸렸다.
- 일부 테스트 케이스는 html태그가 약간 다른지 정규식으로 안하면 틀렸다.
- 9번과 10번은 정규식으로 하니 바로 풀렸지만, https://를 기준으로 나누면 틀린답을 보여줬다.
- 다른 사람은 http로 나눠서 정답인걸 보니, https냐 http냐 http가 없냐로 테스트케이스를 만들었나?
- 가끔 제공되는 테스트케이스는 정답이어도 실제 돌린 테스트케이스에서 틀리는 경우가 있다.
- 만약 이게 시험이면 틀린답이 된다….
- 이런 모든 조건도 다 파악하는 능력도 중요하지만, 시험이라는 환경과 연습이라는 환경에서는 다양한 예시가 제공됐으면 하는 바람이다.
- 9번과10만 틀리니 막막했었다.
- 이런문제는 시간이 오래걸리지만 구현하는 재미가 있어 연습할때는 재밌다. 시험때는 노잼임.
아이디어