[프로그래머스] LV.3 매칭점수 (JS)

KG·2021년 5월 7일
Lv.3알고리즘카카오파싱프로그래머스
1

알고리즘

목록 보기
45/61
post-thumbnail

문제

프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.

  • 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
  • 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
  • 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
  • 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
  • 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.

검색어 word와 웹페이지의 HTML 목록인 pages가 주어졌을 때, 매칭점수가 가장 높은 웹페이지의 index를 구하라. 만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 구하라.

제한

  • pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고, 길이는 1 이상 20 이하이다.

  • 한 웹페이지 문자열의 길이는 1 이상 1,500 이하이다.

  • 웹페이지의 index는 pages 배열의 index와 같으며 0부터 시작한다.

  • 한 웹페이지의 url은 HTML의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.

    • 예를들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은 https://careers.kakao.com/index 이다.
    • <meta property="og:url" content="https://careers.kakao.com/index" />

  • 한 웹페이지에서 모든 외부 링크는 <a href="https://careers.kakao.com/index"\>의 형태를 가진다.

    • <a> 내에 다른 attribute가 주어지는 경우는 없으며 항상 href로 연결할 사이트의 url만 포함된다.
    • 위의 경우에서 해당 웹페이지는 https://careers.kakao.com/index 로 외부링크를 가지고 있다고 볼 수 있다.

  • 모든 url은 https:// 로만 시작한다.

  • 검색어 word는 하나의 영어 단어로만 주어지며 알파벳 소문자와 대문자로만 이루어져 있다.

  • word의 길이는 1 이상 12 이하이다.

  • 검색어를 찾을 때, 대소문자 구분은 무시하고 찾는다.

    • 예를들어 검색어가 blind일 때, HTML 내에 Blind라는 단어가 있거나, BLIND라는 단어가 있으면 두 경우 모두 해당된다.

  • 검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영한다.

    • 단어는 알파벳을 제외한 다른 모든 문자로 구분한다.
    • 예를들어 검색어가 "aba" 일 때, "abab abababa"는 단어 단위로 일치하는게 없으니, 기본 점수는 0점이 된다.
    • 만약 검색어가 "aba" 라면, "aba@aba aba"는 단어 단위로 세개가 일치하므로, 기본 점수는 3점이다.

  • 결과를 돌려줄때, 동일한 매칭점수를 가진 웹페이지가 여러 개라면 그중 index 번호가 가장 작은 것를 리턴한다

    • 즉, 웹페이지가 세개이고, 각각 매칭점수가 3,1,3 이라면 제일 적은 index 번호인 0을 리턴하면 된다.

입출력 예시

  • word : blind
  • pages :
["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://a.com\"/>\n</head>  \n<body>\nBlind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. \n<a href=\"https://b.com\"> Link to b </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://b.com\"/>\n</head>  \n<body>\nSuspendisse potenti. Vivamus venenatis tellus non turpis bibendum, \n<a href=\"https://a.com\"> Link to a </a>\nblind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.\n<a href=\"https://c.com\"> Link to c </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n  <meta charset=\"utf-8\">\n  <meta property=\"og:url\" content=\"https://c.com\"/>\n</head>  \n<body>\nUt condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind\n<a href=\"https://a.com\"> Link to a </a>\n</body>\n</html>"]
  • pages는 다음과 같이 3개의 웹페이지에 해당하는 HTML 문자열이 순서대로 들어있다.
<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://a.com"/>
</head>  
<body>
Blind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. 
<a href="https://b.com"> Link to b </a>
</body>
</html>
<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://b.com"/>
</head>  
<body>
Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum, 
<a href="https://a.com"> Link to a </a>
blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.
<a href="https://c.com"> Link to c </a>
</body>
</html>
<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
  <meta charset="utf-8">
  <meta property="og:url" content="https://c.com"/>
</head>  
<body>
Ut condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind
<a href="https://a.com"> Link to a </a>
</body>
</html>

풀이

2019 카카오 블라인드 테스트에서 출제된 문제이다. 대단히 어려운 알고리즘이나 사고력을 요구하는 문제는 아니지만 구현력을 꽤나 요구하는 문제이다. 제한 조건의 요구사항도 매우 많아서 하나라도 놓치면 통과가 되지 않을까하는 두려움도 생긴다. 기본적으로 HTML 파싱과 관련된 문제이고 프론트엔드 개발자라면 조금 용이하게 접근이 가능하지 않을까 생각해본다. 제공되는 테스트 케이스가 살짝 문제 정의와 동떨어진 감이 있다. 그래서 파싱을 아주 최대한 HTML 구조와 동일하게 일치시켜주어야 통과할 확률이 높아진다.

정규식

정규식을 이용해서 문제에서 요구하는 조건을 걸러주도록 하자. 정규식과 관련해서는 해당 포스트에서 간단히 언급한 바가 있다. 특히 해당 문제는 HTML 구조를 적절하게 파싱해야 하므로 정규식을 이용하면 보다 용이하게 문제를 풀 수 있다.

먼저 검색어 word는 문제 조건에 따라 대소문자 구분은 무시하고 찾는다. 따라서 먼저 소문자로 통일시켜서 매칭을 진행하도록 하자.

word = word.toLowerCase();	// 소문자로 통일

먼저 검색어와 완전히 일치하는 내용을 찾아야 하는데, 대상은 <body> 태그 안에 담긴 내용만 타겟으로 한다. 또한 내용에 담긴 각 문자열은 대소문자 구분 없이 완전히 일치해야 한다. 따라서 숫자, 특수기호와 같은 표현들은 모두 걸러주어야 한다. 이때 정규식 표현을 split() 함수에 인자로 이용하면 해당 문자열을 정규식과 일치하는 값을 기준으로 걸러서 배열의 형태로 반환하게 된다. 예를 들어 아래의 경우 다음과 같은 결과가 반환된다.

// 정규식 = 특수기호 매칭
const result = "abc#abc abc".split(정규식);

// result = ['abc', 'abc', 'abc'];

따라서 숫자와 특수기호를 모두 찾아주는 정규식을 다음과 같이 만들어주자.

// 숫자와 특수기호를 찾는 정규식
// \d는 숫자 문자에 대응, \W는 단어 문자가 아닌 문자에 대응
const REGEX_WORD = /[\d|\W]/;

또한 링크점수를 매기기 위해서 링크가 걸린 태그를 구분해주는 정규식이 필요하다. 링크의 경우는 항상 <a href='https:someURL' />의 형태를 가지기 때문에 다음과 같이 정규식을 선언해주자.

// 외부링크를 찾는 정규식
// \S는 공백문자가 아닌 하나의 문자에 대응 + *는 연속 반복에 대응
// url은 특수기호 및 숫자, 영대소문자 등 다양한 문자가 가능하므로
// 공백문자가 아닌 문자로 접근하면 올바르게 접근이 가능하다.
const REGEX_URL = /<a href="https:\S*"/gi;

처음엔 href 로만 접근했는데 정상적으로 값을 가져오지 못하는 테스트케이스가 존재한다. 따라서 꼭 태그까지 같이 합쳐 <a href= "..." 형태로 접근하도록 하자!

다음은 메타태그 내에 존재하는 나의 url 을 파싱할 수 있어야 한다. 이때 해당 정보는 굳이 정규식을 이용하지 않아도 상관없다. 이 경우에는 항상 meta property 라는 속성으로 고정된 형태로 지정되기 때문이다. 따라서 그냥 문자열을 할당해주자. 그리고 url의 순수한 경로는 위에서 만들어준 REGEX_URL과 유사하게 그러나 태그정보만 제외해서 가져올 수 있다.

// 자기 페이지의 url 매칭
const META_URL = 'meta property';

HTML 파싱

위의 정규식과 문자열을 가지고 HTML을 파싱해주자. 파싱은 다음의 단계로 이루어져야 한다.

  1. 페이지 태그 구분 : \n 키워드로 구분 가능
  2. 자기페이지의 url 파싱
  3. <body> 내부 내용 파싱
  4. 파싱된 내용으로 기본점수와 외부링크 점수를 계산

위의 과정으로 파싱된 내용을 저장하기 위해 Map 자료구조를 사용해서 정보를 저장하자. 또는 객체(Object) 자료구조를 사용해도 상관없다.

...
const pageInfo = new Map();

peges.forEach((page, idx) => {
  // 페이지의 태그를 기준으로 분할
  const pageArr = page.split('\n');
  // 자기 페이지의 인덱스를 찾아
  const urlIdx = pageArr.findIndex(el => el.includes(META_URL));
  // 현재 페이지의 url 값만 저장 (정규식 이용)
  const pageURL = pageArr[urlIdx].match(/https:\S*/gi)[0];
  // body 태그의 시작과 끝 부분의 인덱스를 찾아
  const bodyStart = pageArr.findIndex(el => el.includes('<body>'));
  const bodyEnd = pageArr.findIndex(el => el.includes('</body>'));
  // body 태그 내용에 해당하는 부분만 저장
  const body = pageArr.slice(bodyStart+1, bodyEnd);
  // 기본점수와 외부링크 모두 flatMap을 이용하여 1차원 배열 접근
  // 기본점수는 숫자, 특수기호를 제외한 내용 중에
  // 현재 검색어와 대소문자 구분없이 정확히 일치하는 개수
  const point = body.flatMap(str => str.toLowerCase().split(REGEX_WORD)).filter(e => e === word).length;
  // 외부링크는 REGEX_URL에 따라 1차로 걸러지고
  // undefined 값은 filter로 한번 걸러준 뒤
  // `<a href=` 정보는 날려서 url 경로만 저장 
  const outLinks = body.flatMap(str => str.match(REGEX_URL)).filter(e => e).map(e => e.substr(8, e.length));
  // 페이지에 대한 정보 저장
  // 현재 경로 : { 기본점수, 외부링크, 해당 경로의 인덱스, 매치포인트 }
  pageInfo.set(pageURL, { point, outLinks, idx, matchPoint: 0 });
});

점수계산

위의 연산을 모두 마치고나면 pageInfo에는 url을 키 값으로 하여 기본점수, 외부링크 경로, 인덱스 그리고 매치포인트 점수가 담기게 된다. 따라서 해당 정보를 가지고 각 페이지의 매칭점수를 계산해줄 수 있다.

매칭 점수는 다음의 과정을 거쳐 계산된다.

  1. 기본점수 (검색어 일치 개수) : point에 저장됨
  2. 외부링크 개수 (개수당 1점) : outLinks의 크기와 동일
  3. 링크점수 : 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 / 외부 링크 수의 총합
  4. 매칭점수 : 기본점수 + 링크점수

이때 1번과 2번은 위의 과정에서 이미 계산되어 담겨있으므로 3번과 4번에 대한 과정을 추가로 계산해주자.

for(const [key, value] of pageInfo) {
  // 3번 링크점수 계산 (현재 페이지의 기본점수 / 링크 수)
  // 해당 값을 링크가 향하는 경로의 매치포인트에 더해주어야 함
  const linkPoint = value.point / value.outLinks.lnegth;
  
  // 현재 페이지와 연결되어 있는 링크를 찾아서
  for(const link of value.outLinks) {
    if(pageInfo.has(link)) {
      const origin = pageInfo.get(link);
      // 기존 매칭점수가 있는 경우 이미 기본점수가 연산되어 있으므로
      // 매칭점수 + 링크점수를 더해주고
      // 그 외의 경우엔 기본점수 + 링크점수를 매칭점수로 더해주어
      const calculatedPoint = origin.matchPoint 
      	? origin.matchPoint + linkPoint 
      	: origin.point + linkPoint;
      // 해당 링크의 매치포인트를 갱신한다
      pageInfo.set(link, { ...origin, matchPoint: calculatedPoint }); 
    }
  }
}

정답 반환

거의 다 왔지만 아직 끝이 아니다. 문제에서는 매칭점수가 가장 높은 웹페이지의 인덱스를 요구하고 있기 때문이다. 때문에 위에서 연산에 따로 쓰이지 않은 인덱스 값을 따로 저장해주었다.

이미 매칭점수는 위에서 다 구해주었기 때문에, 매칭점수를 기준으로 내림차순 정렬을 해주도록 하자. 이때 같은 매칭점수를 가지는 경우엔 더 낮은 인덱스를 반환해야 하므로 이를 고려하여 정렬해주면 된다.

// 정답을 담을 배열 선언
const answer = [];

for(const [key, value] of pageInfo) {
  const { point, idx, matchPoint } = value;
  // 최종 매칭점수는 0이 아니면 매칭점수
  // 0인 경우는 기본점수와 같다.
  const finalPoint = matchPoint ? matchPoint : point;
  // 인덱스와 최종 매칭점수를 배열 형태로 삽입
  answer.push([idx, finalPoint]);
}

// 매칭점수 기준으로 내림차순 정렬
// 만약 매칭점수가 동일하다면 인덱스 순으로 오름차순 정렬
answer.sort((a, b) => a[1] === b[1] ? a[0] - b[0] : b[1] - a[1]);

// 따라서 가장 첫 원소의 처음 값을 반환하면 된다.
return answer[0][0];

전체코드

문제의 지문을 잘 파악하고 그에 맞춰 구현하면 되는 문제이다. 크게 알고리즘적으로 어려운 사항은 없었지만 지문 해석을 자칫 잘못하면 굉장히 오랜 시간이 소요될 수 있을 법도 하다. 꼼꼼히 문제에서 요구하는 바를 잘 분석하여 조건에 맞게 차근차근 구현해나간다면 쉽게 해결할 수 있을 듯 하다. 주석을 제외한 전체코드는 다음과 같다.

function solution (word, pages) {
  word = word.toLowerCase();
  const REGEX_WORD = /[\d|\W]/;
  const REGEX_URL = /<a href="https:\S*"/gi;
  const META_URL = 'meta property';
  const pageInfo = new Map();
  
  pages.forEach((page, idx) => {
    const pageArr = page.split('\n');
    const urlIdx = pageArr.findIndex(el => el.includes(META_URL));
    const pageURL = pageArr[urlIdx].match(/"https:\S*"/gi)[0];
    const bodyStart = pageArr.findIndex(el => el.includes("<body>"));
    const bodyEnd = pageArr.findIndex(el => el.includes("</body>"));
    const body = pageArr.slice(bodyStart+1, bodyEnd);
    const point = body.flatMap(str => str.toLowerCase().split(REGEX_WORD)).filter(e => e === word).length;
    const outLinks = body.flatMap(str => str.match(REGEX_URL)).filter(e => e).map(e => e.substr(8, e.length));
    
    pageInfo.set(pageURL, { point, outLinks, idx, matchPoint : 0 });
  });
  
  for(const [key, value] of pageInfo) {
    const linkPoint = value.point / value.outLinks.length;
    
    for(const link of value.outLinks) {
      if(pageInfo.has(link)) {
        const origin = pageInfo.get(link);
        const calculatedPoint = origin.matchPoint 
        	? origin.matchPoint + linkPoint
        	: origin.point + linkPoint;
        pageInfo.set(link, { ...origin, matchPoint: calculatedPoint });
      }
    }
  }
  
  const answer = [];
  
  for(const [key, value] of pageInfo) {
    const { point, idx, matchPoint } = value;
    const finalPoint = matchPoint ? matchPoint : point;
    answer.push([ idx, finalPoint ]);
  };
  
  answer.sort((a, b) => a[1] === b[1] ? a[0] - b[0] : b[1] - a[1]);
  
  return answer[0][0];
}

출처

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

profile
KG
개발잘하고싶다
이전 포스트

[프로그래머스] LV.3 징검다리 건너기 (JS)

다음 포스트

[프로그래머스] LV.4 징검다리 (JS)

0개의 댓글