🏅 프로그래머스 42893 : 매칭 점수 - Javascript

2023-03-01

#알고리즘 #프로그래머스

문제 설명

출처: 프로그래머스 42893 : 매칭 점수

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

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

예를 들어, 다음과 같이 A, B, C 세 개의 웹페이지가 있고, 검색어가 hi라고 하자.

이때 A 웹페이지의 매칭점수는 다음과 같이 계산할 수 있다.

기본 점수는 각 웹페이지에서 hi가 등장한 횟수이다.
- A,B,C 웹페이지의 기본점수는 각각 1점, 4점, 9점이다.
외부 링크수는 다른 웹페이지로 링크가 걸린 개수이다.
- A,B,C 웹페이지의 외부 링크 수는 각각 1점, 2점, 3점이다.
A 웹페이지로 링크가 걸린 페이지는 B와 C가 있다.
- A 웹페이지의 링크점수는 B의 링크점수 2점(4 ÷ 2)과 C의 링크점수 3점(9 ÷ 3)을 더한 5점이 된다.
그러므로, A 웹페이지의 매칭점수는 기본점수 1점 + 링크점수 5점 = 6점이 된다.

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

제한사항

pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고, 길이는 $1$ 이상 $20$ 이하이다.
한 웹페이지 문자열의 길이는 $1$ 이상 $1,500$ 이하이다.
웹페이지의 index는 pages 배열의 index와 같으며 $0$ 부터 시작한다.
한 웹페이지의 url은 HTML의 태그 내에 태그의 값으로 주어진다.
- 예를들어, 아래와 같은 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을 리턴하면 된다.

입출력 예

예시 #1

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>

위의 예를 가지고 각각의 점수를 계산해보자.

기본점수 및 외부 링크수는 아래와 같다.
- a.com의 기본점수는 3, 외부 링크 수는 1개
- b.com의 기본점수는 1, 외부 링크 수는 2개
- c.com의 기본점수는 1, 외부 링크 수는 1개
링크점수는 아래와 같다.
- a.com의 링크점수는 b.com으로부터 0.5점, c.com으로부터 1점
- b.com의 링크점수는 a.com으로부터 3점
- c.com의 링크점수는 b.com으로부터 0.5점
각 웹 페이지의 매칭 점수는 다음과 같다.
- a.com : 4.5 점
- b.com : 4 점
- c.com : 1.5 점

따라서 매칭점수가 제일 높은 첫번째 웹 페이지의 index인 0을 리턴 하면 된다.

예시 #2

word : Muzi

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://careers.kakao.com/interview/list"/>\n</head>  \n<body>\n<a href="https://programmers.co.kr/learn/courses/4673"></a>#!MuziMuzi!)jayg07con&&\n\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://www.kakaocorp.com"/>\n</head>  \n<body>\ncon%\tmuzI92apeach&2<a href="https://hashcode.co.kr/tos"></a>\n\n\t^\n</body>\n</html>"
]

pages는 다음과 같이 2개의 웹페이지에 해당하는 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://careers.kakao.com/interview/list"/>
</head>
<body>
<a href="https://programmers.co.kr/learn/courses/4673"></a>#!MuziMuzi!)jayg07con&&

</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://www.kakaocorp.com"/>
</head>
<body>
con%    muzI92apeach&2<a href="https://hashcode.co.kr/tos"></a>

    ^
</body>
</html>

위의 예를 가지고 각각의 점수를 계산해보자.

기본점수 및 외부 링크수는 아래와 같다.
- careers.kakao.com/interview/list 의 기본점수는 0, 외부 링크 수는 1개
- www.kakaocorp.com 의 기본점수는 1, 외부 링크 수는 1개
링크점수는 아래와 같다.
- careers.kakao.com/interview/list 의 링크점수는 0점
- www.kakaocorp.com 의 링크점수는 0점
각 웹 페이지의 매칭 점수는 다음과 같다.
- careers.kakao.com/interview/list : 0점
- www.kakaocorp.com : 1 점

따라서 매칭점수가 제일 높은 두번째 웹 페이지의 index인 1을 리턴 하면 된다.

풀이 과정

특별한 알고리즘이 필요하기보단 문자열 파싱을 잘 해야하는 문제라 별 고민 없이 코드를 작성했습니다.

먼저 아래와 같이 페이지 값을 파싱하는 함수를 작성했습니다.

const parsePage = (page, index, word) => {
  //페이지의 주소와 외부 링크는 정규식을 통해 찾을 수 있다
  const url = page.match(/<meta property="og:url" content="(.+?)"/i)[1];

  //페이지의 body 내용을 가져와 미리 소문자화한다
  let body = page.match(/<body>([wW]+)</body>/i)[1].toLowerCase();

  //replaceAll의 콜백 함수로 외부 링크를 수집하고 body에서 제거
  const externalUrls = [];
  body = body.replaceAll(/<a href="(.+?)">/gi, (_, externalUrl) => {
    externalUrls.push(externalUrl);
    return '';
  });

  //앞뒤가 영문자가 아닌데, 단어와 일치하는 경우의 갯수를 기본 점수로 사용
  const basePoint = (body.match(new RegExp(`[^a-z]${word}[^a-z]`, 'ig')) || [])
    .length;

  //파싱 결과를 객체로 반환
  return {
    index,
    url,
    externalUrls,
    basePoint,
    totalPoint: basePoint
  };
};

그 후 페이지를 파싱한 결과를 Map에 담았습니다. 원래 배열을 사용하려고 했는데, 외부 링크 점수를 계산할 때 url을 키로 사용하기 위해 Map을 사용했습니다.

매핑이 끝난 후에 외부 링크 점수를 totalPoint에 더해 총 점수를 계산하고, 총점수를 기준으로 내림차순 정렬한 결과의 첫번째 요소의 인덱스를 반환했습니다.

function solution(word, pages) {
  //입력된 데이터 분석 후 매핑
  const pageInfos = new Map(
    pages.map((page, index) => {
      const parsed = parsePage(page, index, word);
      return [parsed.url, parsed];
    })
  );

  //외부 링크 점수 부여 처리
  for (const page of pageInfos.values()) {
    const additionalPoint = page.basePoint / page.externalUrls.length;
    for (const externalUrl of page.externalUrls) {
      if (pageInfos.has(externalUrl)) {
        pageInfos.get(externalUrl).totalPoint += additionalPoint;
      }
    }
  }

  //총점수를 내림차순으로 정렬하고 첫번째 페이지의 인덱스를 반환
  return [...pageInfos.values()].sort((a, b) => b.totalPoint - a.totalPoint)[0]
    .index;
}

하지만 이렇게 작성한 코드의 경우 입력 예제 2가지는 통과했지만, 테스트 케이스 1,2,9,12를 통과하지 못해 실패했습니다. 테스트케이스는 비공개이기 때문에 어떤 입력에 실패하는지 직접 찾아 해결해야만 했습니다. 때문에 문제에 적힌 모든 조건의 반례가 될만한 테스트 케이스를 직접 추가해서 실행해봤습니다. 그러던 중 문제 조건의 예를들어 검색어가 "aba" 일 때, "abab abababa"는 단어 단위로 일치하는게 없으니, 기본 점수는 0점이 된다라는 부분을 구현한 테스트 케이스를 추가한 순간 드디어 제 코드가 통과하지 못하는 테스트케이스를 찾게 되었습니다.

원인은 바로 기본 점수를 계산하는 부분에서 저지른 실수 때문이였습니다.

const basePoint = (body.match(new RegExp(`[^a-z]${word}[^a-z]`, 'ig')) || [])
  .length;

단순히 body태그 내에는 최소한 단어 양쪽에 띄어쓰기라도 있을테니 앞뒤가 영문자가 아닌데, word와 일치하면 될거라고 생각했었는데, 이렇게 처리하는 경우 영문자 사이에 한글자만 존재하는 경우 다음 영문자를 그냥 넘어가는 경우가 발생했습니다.

예를 들어 1abc2def3ghi4라는 문자열에 대해 정규식 /[^a-z][a-z]+[^a-z]/g 를 처리하면 결과는 ['1abc2', '3ghi4']입니다. 2def3이 포함되지 않은 이유는 정규식이 아래와 같이 작동하기 때문입니다.

처리중인 문자	…	확인중인 문자열	남은 문자열
`1`	`[^a-z]`일치	`1`	`abc2def3ghi4`
`a`	`[a-z]+`일치	`1a`	`bc2def3ghi4`
`b`	`[a-z]+`일치	`1ab`	`c2def3ghi4`
`c`	`[a-z]+`일치	`1abc`	`2def3ghi4`
`2`	`[^a-z]`일치 - 매칭 완료	`1abc2`	`def3ghi4`

`d`	`[^a-z]`불일치		`ef3ghi4`
`e`	`[^a-z]`불일치		`f3ghi4`
`f`	`[^a-z]`불일치		`3ghi4`

`3`	`[^a-z]`일치	`3`	`ghi4`
`g`	`[a-z]+`일치	`3g`	`hi4`
`h`	`[a-z]+`일치	`3gh`	`i4`
`i`	`[a-z]+`일치	`3ghi`	`4`
`4`	`[^a-z]`일치 - 매칭 완료	`3ghi4`

고래 싸움에 새우 def는 등이 터져버렸습니다!

이런 문제를 해결하기 위해 모든 영단어를 가져온 뒤 찾아야할 단어와 비교해 일치하는 횟수를 기본점수로 사용하도록 아래와 같이 수정했고, 이제 모든 테스트 케이스를 잘 통과합니다.

const basePoint = body
  .match(/[a-z]+/gi)
  .filter((match) => match === word.toLowerCase()).length;

다른 분들은 저처럼 정규식을 잘 모르면서 정규식을 맹신하는 일이 없길 바랍니다… 이걸 몰라서 코드의 온갖 부분을 다 갈아 엎고 난리 쳤어요ㅠㅠ

최종 코드

const parsePage = (page, index, word) => {
  //페이지의 주소와 외부 링크는 정규식을 통해 찾을 수 있다
  const url = page.match(/<meta property="og:url" content="(.+?)"/i)[1];

  //페이지의 body 내용을 가져와 미리 소문자화한다
  let body = page.match(/<body>([wW]+)</body>/i)[1].toLowerCase();

  //replaceAll의 콜백 함수로 외부 링크를 수집하고 body에서 제거
  const externalUrls = [];
  body = body.replaceAll(/<a href="(.+?)">/gi, (_, externalUrl) => {
    externalUrls.push(externalUrl);
    return '';
  });

  //body의 모든 영단어를 검사해 페이지의 기본 점수를 계산
  const basePoint = body
    .match(/[a-z]+/gi)
    .filter((match) => match === word.toLowerCase()).length;

  return {
    index,
    url,
    externalUrls,
    basePoint,
    totalPoint: basePoint
  };
};

function solution(word, pages) {
  //입력된 데이터 분석 후 매핑
  const pageInfos = new Map(
    pages.map((page, index) => {
      const parsed = parsePage(page, index, word);
      return [parsed.url, parsed];
    })
  );

  //매핑된 데이터로 외부 링크 점수 부여 처리
  for (const page of pageInfos.values()) {
    const additionalPoint = page.basePoint / page.externalUrls.length;
    for (const externalUrl of page.externalUrls) {
      if (pageInfos.has(externalUrl)) {
        pageInfos.get(externalUrl).totalPoint += additionalPoint;
      }
    }
  }

  //총점수를 내림차순으로 정렬하고 첫번째 페이지의 인덱스를 반환
  return [...pageInfos.values()].sort((a, b) => b.totalPoint - a.totalPoint)[0]
    .index;
}