[프로그래머스] 42893 매칭 점수 (JavaScript)

문제

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

풀이

제한 조건이 까다로운 구현 중심의 문제였다.

최대 20개의 페이지와 페이지당 1500자 정도의 HTML이 주어지므로, $O(n^2)$ 정도의 시간복잡도를 가진 구현도 충분히 통과할 수 있다고 판단했다. 따라서 시간 복잡도는 우선적인 고려 사항에서 제외하고 구현의 정확성에 집중했다.

다만 입력 크기와 별개로, 문제에서 제시한 HTML 형식이 어디까지 정형화되어 있는지 판단하기 어려운 부분이 있어 구현에는 꽤 오랜 시간이 걸렸다.

처음에는 정규표현식을 바로 사용하지 않았다. 문자열을 순회하며 토큰화하고, 현재 head, meta, body, a 태그 내부인지 여부를 상태 flag로 관리하는 방식을 먼저 구현했다. 순회 포인터의 위치를 기준으로 태그의 시작과 끝, 속성 값, 본문 텍스트를 구분하면서 URL, 외부 링크, 기본 점수를 각각 추출하려고 했다.

다만 구현을 진행할수록, HTML 형식의 보장 범위에 따라 방어해야 할 예외가 계속 늘어났다. 태그의 속성 순서, 공백, 대소문자, 태그 중첩, head와 body의 구조 등을 어느 수준까지 직접 파싱해야 하는지 명확하지 않았고, 아래와 같은 해석 문제도 있었다.

pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고
- HTML 형식의 웹페이지는 어느 정도까지 무엇을 보장해주는가?
- html, head, body 태그는 반드시 한 개 존재하며, 순서도 보장되는가?
한 웹페이지의 url은 HTML의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.
- head 태그 내부에서 URL을 포함한 meta 태그는 반드시 한 개 존재하는가?
- 여러 개 존재할 수 있다면 어떤 태그를 기준으로 판단해야 하는가?
검색어와 링크는 body 내부의 값만 대상으로 간주하는가? head 내부의 값도 포함하는가?
링크 내부에 일치하는 검색어가 있다면 점수에 포함되는가?
- <a href="https://muzi.com">muzi</a>에서 검색어가 muzi라면 여기서 획득하는 점수는 0점, 1점, 2점 중 무엇인가?

포인터 기반 파서를 꽤 오래 다듬었지만, 문제에서 요구하는 입력 범위에 비해 구현이 과도하게 복잡해지고 있다는 느낌이 들었다. 모든 HTML 예외를 직접 처리하기보다, 문제에서 제시한 형식이 충분히 정형화되어 있다고 가정하고 필요한 값만 추출하는 편이 더 현실적이라고 판단했다.

결국 기존 파서는 엎고, 문제에서 제시한 입력 형식이 크게 흔들리지 않을 것이라는 전제 아래 정규표현식으로 필요한 부분만 뽑아냈다. URL, 외부 링크, 태그를 제거한 텍스트를 각각 분리해 추출하는 방식이다.

엄밀하게 HTML을 파싱했다기보다, 테스트 케이스가 문제에서 정한 형식을 지켜 줄 것이라는 가정에 기대어 정규표현식으로 밀어붙인 셈이라 개인적으로는 조금 찜찜한 풀이였다. 그래도 상태를 세밀하게 관리하는 파서를 계속 붙잡고 있기보다, 제한된 입력 형식 안에서 필요한 값만 추출해 문제를 끝내는 쪽을 선택했다.

문제를 맞추긴 했지만, 코딩 테스트 관점에서 접근했을 때 해석이 갈릴 수 있는 지점이 적지 않은 문제라고 생각한다.

정규표현식은 생성형 AI의 도움을 받아 구현했다. 다만 해당 시험 환경과 비슷한 조건에서 정규표현식을 스스로 구성하기 어렵다면, 이 문제를 어떤 방식으로 풀어야 할지는 충분히 고민해 볼 필요가 있다.

정규표현식 구현에 익숙하다면, 알고리즘 문제 해결 관점에서 특별히 어려운 부분은 많지 않은 문제였다.

소스 코드

javascript

const parse = (page, word) => {
    const [, head] = page.match(/<head\b[^>]*>([\s\S]*?)<\/head>/i);
    const [, url] = head.match(/<meta\s+property="og:url"\s+content="(https:\/\/[^"]+)"/i);
    const links = Array.from(
        page.matchAll(/<a href="(https:\/\/[^"]+)">/gi),
        ([, link]) => link
    );
    const text = page.replace(/<[^>]*>/g, " ");
    const wordRegExp = new RegExp(
        `(^|[^a-z])${word.replace(/[.*+?^${}()|[\]\\]/g, "\\$&")}(?=[^a-z]|$)`,
        "gi"
    );
    const base = (text.match(wordRegExp) ?? []).length;

    return { url, links, base };
};

const solution = (word, pages) => {
    const data = new Map(
        pages.map((page, index) => {
            const { url, links, base } = parse(page, word);
            return [ url, { links, base, index, share: 0 }];
        })
    );

    for (const [ url, { base, links }] of data) {
        for (const link of links) {
            const target = data.get(link);
            if (target) target.share += base / links.length;
        }
    }
    
    return data.values().reduce(
        (best, current) => 
            best === undefined || best.base + best.share < current.base + current.share ? current : best
        ,undefined
    ).index;
};

[프로그래머스] 42893 매칭 점수 (JavaScript)

문제

풀이

소스 코드

Share this post