[프로그래머스] 매칭 점수

페이지 랭킹 알고리즘 구현 과정 블로그

문제 이해

웹 페이지의 검색 순위를 결정하는 알고리즘을 구현해야 합니다. 각 페이지는 기본 점수와 링크 점수를 가지며, 최종 점수가 가장 높은 페이지의 인덱스를 반환해야 합니다.

1단계: 기본 점수 계산 함수 구현

function parsingKeyword(str, parseStr) {
  // 알파벳이 아닌 문자를 구분자로 사용해서 문자열을 분리
  const words = str.split(/[^a-zA-Z]/).filter((word) => word.length > 0);

  let count = 0;

  // 각 단어가 파싱 문자열과 정확히 일치하는지 확인 (대소문자 구분 안함)
  for (let word of words) {
    if (word.toLowerCase() === parseStr.toLowerCase()) {
      count++;
    }
  }

  return count;
}

구현 과정:

• 정규표현식 /[^a-zA-Z]/을 사용해 알파벳이 아닌 문자를 구분자로 활용
• 빈 문자열 필터링으로 의미있는 단어만 추출
• 대소문자 구분 없이 정확히 일치하는 단어 개수 반환

2단계: 페이지 URL 추출 함수 구현

function findMyLink(htmlStr) {
  // '<meta property="og:url"' 패턴을 찾기
  const metaPattern = '<meta property="og:url"';

  for (let i = 0; i <= htmlStr.length - metaPattern.length; i++) {
    if (htmlStr.substring(i, i + metaPattern.length) === metaPattern) {
      // 해당 위치부터 시작해서 content= 찾기
      let start = i + metaPattern.length;

      // content= 패턴 찾기
      const contentPattern = 'content="';
      for (let j = start; j <= htmlStr.length - contentPattern.length; j++) {
        if (
          htmlStr.substring(j, j + contentPattern.length) === contentPattern
        ) {
          // content=" 다음부터 시작
          let contentStart = j + contentPattern.length;
          let contentEnd = contentStart;

          // 닫는 따옴표 찾기
          while (contentEnd < htmlStr.length && htmlStr[contentEnd] !== '"') {
            contentEnd++;
          }

          // content 값 추출
          return htmlStr.substring(contentStart, contentEnd);
        }
      }
    }
  }

  return null; // 찾지 못한 경우
}

구현 과정:

• HTML 문자열에서 <meta property="og:url" 패턴을 순차적으로 검색
• 해당 패턴을 찾으면 content=" 패턴을 찾아 URL 추출
• 문자열 파싱을 위해 인덱스 기반 접근 방식 사용

3단계: 외부 링크 확인 함수 구현

function findextLnk(htmlStr, searchTerm) {
  // '<a href="' 패턴을 찾기
  const hrefPattern = '<a href="';

  for (let i = 0; i <= htmlStr.length - hrefPattern.length; i++) {
    if (htmlStr.substring(i, i + hrefPattern.length) === hrefPattern) {
      // href=" 다음부터 시작
      let hrefStart = i + hrefPattern.length;
      let hrefEnd = hrefStart;

      // 닫는 따옴표 찾기
      while (hrefEnd < htmlStr.length && htmlStr[hrefEnd] !== '"') {
        hrefEnd++;
      }

      // href 값 추출
      let hrefValue = htmlStr.substring(hrefStart, hrefEnd);

      // 검색어와 일치하는지 확인
      if (hrefValue === searchTerm) {
        return true;
      }
    }
  }

  return false;
}

구현 과정:

• HTML에서 <a href=" 패턴을 찾아 링크 URL 추출
• 추출한 URL이 검색 대상과 정확히 일치하는지 확인
• 첫 번째 일치하는 링크를 찾으면 즉시 true 반환

4단계: 외부 링크 수 계산 함수 구현

function countAHref(htmlStr) {
  let count = 0;
  const pattern = "<a href";

  for (let i = 0; i <= htmlStr.length - pattern.length; i++) {
    if (htmlStr.substring(i, i + contentPattern.length) === pattern) {
      count++;
    }
  }

  return count;
}

구현 과정:

• HTML 문자열에서 <a href 패턴의 개수를 세어 외부 링크 수 계산
• 간단한 문자열 매칭으로 링크 태그 개수 추출

5단계: 메인 알고리즘 구현

function solution(word, pages) {
  // 1. 기본 점수 구하기
  let baseNum = {};
  let myLink = {};
  let extcs = {};

  for (let page = 0; page < pages.length; page++) {
    let cnt = parsingKeyword(pages[page], word);
    baseNum[page] = cnt;
    let link = findMyLink(pages[page]);
    myLink[page] = link;
    let extLinkCounting = countAHref(pages[page]);
    extcs[page] = extLinkCounting;
  }

  // 2. 링크 점수 계산
  let extLinkCnt = {};
  for (let page = 0; page < pages.length; page++) {
    let myLnk = myLink[page];
    extLinkCnt[page] = {};

    for (let idx = 0; idx < pages.length; idx++) {
      if (idx !== page) {
        extLinkCnt[page][idx] = 0;
      }
    }

    for (let idx = 0; idx < pages.length; idx++) {
      if (idx !== page && findextLnk(pages[idx], myLnk)) {
        extLinkCnt[page][idx] += 1;
      }
    }
  }

  // 3. 최종 점수 계산
  let final = {};
  for (let idx = 0; idx < pages.length; idx++) {
    final[idx] = baseNum[idx];
    for (let idxx = 0; idxx < pages.length; idxx++) {
      if (idxx !== idx) {
        if (extLinkCnt[idx][idxx] >= 1) {
          final[idx] += baseNum[idxx] / extcs[idxx];
        }
      }
    }
  }

  // 4. 최고 점수 인덱스 찾기
  function findMaxIndex(obj) {
    let maxValue = -Infinity;
    let maxIndex = null;

    for (let key in obj) {
      if (obj[key] > maxValue) {
        maxValue = obj[key];
        maxIndex = key;
      }
    }

    return parseInt(maxIndex);
  }

  return findMaxIndex(final);
}

구현 과정에서 발견한 문제점들

1. 치명적인 구조적 오류

• findMaxIndex 함수가 반복문 안에 위치해 첫 번째 페이지에서만 실행됨
• 나머지 페이지들의 점수 계산이 완료되지 않음

2. 링크 점수 계산 로직 오류

• extLinkCnt[idx][idxx]의 의미가 반대로 해석됨
• 실제로는 다른 페이지에서 현재 페이지로 오는 링크를 계산해야 함

3. 나누기 오류 처리 부족

• 외부 링크가 0개인 페이지에서 나누기 시 NaN 발생
• 예외 처리 로직 필요

개선 방향

1. 구조 개선: findMaxIndex 함수를 반복문 밖으로 이동
2. 로직 수정: 링크 점수 계산 방향 정정
3. 예외 처리: 0으로 나누는 경우 처리 추가
4. 코드 최적화: 불필요한 중복 계산 제거

이러한 과정을 통해 페이지 랭킹 알고리즘의 기본 구조를 이해하고, 실제 구현에서 발생할 수 있는 문제점들을 파악할 수 있었습니다.