링크

파일명 정렬 - 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)
  • 매칭점수 계산
    • infoI[1]+linkpoint

후기

  • 이 문제는 그저 로직을 정확하게 구현하면 되는 문제이다.
  • 하지만 난이도를 위해 복잡한 로직을 추가하고, 문제가 엄청 길어서 독해부터 오래걸렸다.
  • 일부 테스트 케이스는 html태그가 약간 다른지 정규식으로 안하면 틀렸다.
    • 9번과 10번은 정규식으로 하니 바로 풀렸지만, https://를 기준으로 나누면 틀린답을 보여줬다.
    • 다른 사람은 http로 나눠서 정답인걸 보니, https냐 http냐 http가 없냐로 테스트케이스를 만들었나?
  • 가끔 제공되는 테스트케이스는 정답이어도 실제 돌린 테스트케이스에서 틀리는 경우가 있다.
    • 만약 이게 시험이면 틀린답이 된다….
    • 이런 모든 조건도 다 파악하는 능력도 중요하지만, 시험이라는 환경과 연습이라는 환경에서는 다양한 예시가 제공됐으면 하는 바람이다.
    • 9번과10만 틀리니 막막했었다.
  • 이런문제는 시간이 오래걸리지만 구현하는 재미가 있어 연습할때는 재밌다. 시험때는 노잼임.

아이디어

  • regex, 정규식