JavaScript 해시 테이블 연습: 정규화 문자열 빈도와 등장 순서

한 파일로 실행하는 전체 정답

'use strict';

class StringHashTable {
  constructor(capacity = 4) {
    if (!Number.isInteger(capacity) || capacity < 1) {
      throw new RangeError('capacity must be a positive integer');
    }
    this.buckets = Array.from({ length: capacity }, () => []);
    this.size = 0;
  }

  normalize(key) {
    if (typeof key !== 'string') throw new TypeError('key must be a string');
    return key.normalize('NFC');
  }

  index(key, capacity = this.buckets.length) {
    let hash = 2166136261;
    for (const character of key) {
      hash = Math.imul(hash ^ character.codePointAt(0), 16777619) >>> 0;
    }
    return hash % capacity;
  }

  resize(capacity) {
    const next = Array.from({ length: capacity }, () => []);
    for (const bucket of this.buckets) {
      for (const entry of bucket) {
        next[this.index(entry.key, capacity)].push(entry);
      }
    }
    this.buckets = next;
  }

  set(rawKey, value) {
    const key = this.normalize(rawKey);
    let bucket = this.buckets[this.index(key)];
    for (const entry of bucket) {
      if (entry.key === key) {
        entry.value = value;
        return this;
      }
    }
    if ((this.size + 1) / this.buckets.length > 0.75) {
      this.resize(this.buckets.length * 2);
      bucket = this.buckets[this.index(key)];
    }
    bucket.push({ key, value });
    this.size += 1;
    return this;
  }

  get(rawKey) {
    const key = this.normalize(rawKey);
    for (const entry of this.buckets[this.index(key)]) {
      if (entry.key === key) return { found: true, value: entry.value };
    }
    return { found: false };
  }

  delete(rawKey) {
    const key = this.normalize(rawKey);
    const bucket = this.buckets[this.index(key)];
    const index = bucket.findIndex(entry => entry.key === key);
    if (index === -1) return false;
    bucket.splice(index, 1);
    this.size -= 1;
    return true;
  }

  entries() {
    const result = [];
    for (const bucket of this.buckets) {
      for (const entry of bucket) result.push([entry.key, entry.value]);
    }
    return result;
  }
}

function solve({ words }) {
  const table = new StringHashTable();
  const order = [];
  for (const word of words) {
    const key = table.normalize(word);
    const previous = table.get(key);
    if (!previous.found) order.push(key);
    table.set(key, previous.found ? previous.value + 1 : 1);
  }
  return order.map(key => [key, table.get(key).value]);
}

module.exports = { solve };

if (require.main === module) {
  const fs = require('node:fs');
  const input = JSON.parse(fs.readFileSync(0, 'utf8').replace(/^\uFEFF/, ''));
  process.stdout.write(JSON.stringify(solve(input)) + '\n');
}

정답 해설: 개수와 순서를 다른 상태에 맡깁니다

table은 정규화 키→빈도 관계를 담당하고 order는 서로 다른 키의 최초 등장 순서를 담당합니다. 리사이즈로 버킷 위치가 달라져도 order 배열은 건드리지 않으므로 출력 순서가 보존됩니다. 테이블의 entries가 삽입 순서를 보장한다고 가정하지 않는 것이 핵심입니다.

단어를 하나 읽을 때 get 결과가 없으면 order에 추가하고 빈도 1을 저장합니다. 있으면 기존 값에 1을 더합니다. 매 단계 “지금까지 읽은 접두 목록의 빈도”를 유지하므로 마지막에는 전체 빈도가 됩니다. 같은 NFC 키를 table 내부에서 다시 정규화해도 결과는 같으며 이 중복 처리는 점근 비용을 바꾸지 않습니다.

최종 결과는 order를 순회하며 table.get으로 현재 빈도를 읽습니다. 버킷을 직접 출력하지 않으므로 강제 충돌이나 리사이즈 횟수와 관계없이 동일한 결과를 냅니다. 갱신은 size를 증가시키지 않고 새 키만 size를 증가시킨다는 클래스 불변식도 유지되어야 합니다.

복잡도와 해시 가정

Q는 입력 단어 수, U는 서로 다른 NFC 키 수, Lmax는 정규화 후 최대 키 길이입니다. 문자열 처리와 비교를 길이에 비례한다고 보는 모델 및 고른 해시 분포 아래 기대 상환 시간은 O(Q·Lmax), 출력 조회는 O(U·Lmax)로 포함됩니다. 키 길이가 제한된 이 문제에서는 보통 기대 O(Q)로 표현할 수 있지만 문자열 길이와 분포 가정을 생략한 최악 보장은 아닙니다.

충돌이 집중되면 전체 처리 최악 O(Q·U·Lmax)가 될 수 있고, 단일 리사이즈는 저장된 키 전체를 재해시합니다. C를 입력 및 정규화 문자열 총 저장량으로 두면 입력·버킷·순서·출력을 포함한 공간은 O(C+Q+U)입니다. 이 클래스는 삭제 시 축소하지 않지만 이 문제는 증가만 하므로 버킷 수가 U에 비례합니다. 고정 개수 버킷에 무조건 O(1) 조회를 주장하지 않습니다.

직접 확인할 경계

words=[], 빈 문자열 반복, 조합형 한글과 완성형 한글, 대소문자 차이, 이모지, 리사이즈를 여러 번 일으키는 서로 다른 문자열을 확인하세요. 내장 Map에 NFC 키를 누적한 결과와 비교하면 빈도와 최초 등장 순서를 함께 검증할 수 있습니다.