[LeetCode] 811. Subdomain Visit Count

문제 요약

"9001 discuss.leetcode.com" 처럼 "방문 횟수 도메인" 형태의 문자열 배열이 주어집니다.

어떤 도메인을 방문하면 그 상위 도메인도 함께 방문한 것으로 칩니다. 예를 들어 discuss.leetcode.com 을 9001번 방문했다면 아래 세 도메인이 모두 9001번씩 방문된 것입니다.

• discuss.leetcode.com
• leetcode.com
• com

모든 입력을 합산해서 도메인별 총 방문 횟수를 같은 형식의 문자열 배열로 반환하면 됩니다. 순서는 상관없습니다.

핵심 아이디어

두 가지만 떠올리면 됩니다.

1. 하위 도메인은 . 바로 다음부터 끝까지 자른 문자열이다.
   도메인을 한 글자씩 훑다가 . 을 만날 때마다 그 뒤를 잘라내면 모든 상위 도메인을 얻을 수 있습니다.
2. 도메인별 합산은 Map 으로 한다.
   도메인을 key, 누적 방문 횟수를 value 로 두고 더해 나갑니다.

discuss.leetcode.com
       ^ 여기서 자르면 → leetcode.com
                ^ 여기서 자르면 → com

풀이 코드

function subdomainVisits(cpdomains: string[]): string[] {
  const visitMap = new Map<string, number>();

  for (const cp of cpdomains) {
    const [strFreq, domain] = cp.split(" ");
    const freq = Number(strFreq);

    const subdomains: string[] = [domain];
    for (let i = 0; i < domain.length; i++) {
      if (domain[i] !== ".") continue;
      subdomains.push(domain.slice(i + 1));
    }

    for (const subdomain of subdomains) {
      const nextFreq = (visitMap.get(subdomain) ?? 0) + freq;
      visitMap.set(subdomain, nextFreq);
    }
  }

  const visits: string[] = [];
  for (const [domain, count] of visitMap) {
    visits.push(`${count} ${domain}`);
  }

  return visits;
}

코드 설명

1. 횟수와 도메인 분리

const [strFreq, domain] = cp.split(" ");
const freq = Number(strFreq);

입력이 항상 공백 하나로 구분되므로 split(" ") 한 번이면 충분합니다. 횟수는 문자열이라 Number 로 바꿔 줍니다.

2. 하위 도메인 목록 만들기

const subdomains: string[] = [domain];
for (let i = 0; i < domain.length; i++) {
  if (domain[i] !== ".") continue;
  subdomains.push(domain.slice(i + 1));
}

전체 도메인 자신을 먼저 넣어 두고, . 을 만날 때마다 slice(i + 1) 로 그 뒤쪽을 잘라 추가합니다.

discuss.leetcode.com 이라면 ["discuss.leetcode.com", "leetcode.com", "com"] 이 됩니다.

3. Map 에 누적

const nextFreq = (visitMap.get(subdomain) ?? 0) + freq;
visitMap.set(subdomain, nextFreq);

처음 보는 도메인이면 get 이 undefined 를 돌려주므로 ?? 0 으로 기본값을 줍니다. 덕분에 "있으면 더하고 없으면 새로 넣는" 분기를 한 줄로 쓸 수 있습니다.

4. 결과 형식으로 변환

for (const [domain, count] of visitMap) {
  visits.push(`${count} ${domain}`);
}

Map 을 순회하면서 다시 "횟수 도메인" 형태로 조립하면 끝입니다.

복잡도

입력 개수를 N, 도메인 최대 길이를 L 이라고 하면

• 시간 복잡도: O(N · L). 도메인마다 글자를 한 번씩 훑고, 점 개수(최대 2개)만큼 자릅니다.
• 공간 복잡도: O(N · L). 최악의 경우 모든 하위 도메인이 서로 달라 Map 에 전부 저장됩니다.

마무리

"상위 도메인을 어떻게 뽑아낼까"만 정하면 나머지는 Map 합산이라 어렵지 않은 문제였습니다. split(".") 으로 쪼갠 뒤 다시 join 하는 방법도 있지만, . 위치에서 slice 하는 쪽이 배열을 다시 조립할 필요가 없어 더 단순하게 느껴졌습니다.