D+34 문자열 해싱을 이용한 검색 함수 만들기 풀이 이해

문제

문자열 리스트 stringList와 쿼리 리스트 queryList가 있을 때 각 쿼리 리스트에 있는 문자열이 stringList의 문자열 리스트에 있는지 여부를 확인해야 합니다.
각 문자열에 대해서 문자열의 존재 여부를 리스트 형태로 반환하는 solution() 함수를 작성해주세요


제약조건

• 입력 문자열은 영어 소문자로만 이루어져 있습니다.
• 문자열의 최대 길이는 10^6입니다
• 해시 충돌은 없습니다
• 아래와 같은 문자열 해싱 방법을 활용해서 해싱 함수를 구현하세요
• 다음 식에서 p는 31, m은 1,000,000,007로 합니다.
• hash(s)= (s[0] +s[1]p + s[2]p^2 + ... + s[n-1]*p^(n-1)) mod m
  
  
  입출력의 예
  stringList : ["apple", "banana", "cherry"]
  queryList: ["banana", "kiwi", "melon", "apple"]
  return : [True,false,false,True]

풀이

// 1.polynomial hash를 구현한 부분
function polynomialHash(str) {
  const p=31; // 소수
  const m=1_000_000_007; // 버킷 크기
  let hashValue =0;
  for(let i=0; i<str.length; i++) {
    hashValue = (hashValue*p + str.charCodeAt(i)) % m;
  }
  return hashValue;
}

function solution(stringList, queryList) {
  // 2.stringList의 각 문자열에 대해 다항 해시값을 계산
  const hashList = stringList.map((str)=> polynomialHash(str));
  // 3.queryList의 각 문자열이 stringList에 있는지 확인
  const result=[];
  for (const query of queryList) {
    const queryHash = polynomialHash(query);
    if(hashList.includes(queryHash)){
      result.push(true);
    }
    else{
      result.push(false);
    }
  }
  return result;
}

해석

이전 해시값에 p를 곱하고 현재 문자를 더하는 방식
별도의 거듭제곱 변수가 필요없음
이 방식이 각 문자마다 p의 거듭제곱을 별도로 계산하는 방식보다 더 효율적이다.

• 추가 변수가 필요 없어서 메모리 사용이 더 적다.
• 곱하기 연산 한 번, 더하기 연산 한 번으로 연산 횟수가 적다.

hashValue = (hashValue + charValue * pPower) % m;
pPower = (pPower * p) % m;

예시로 보는 계산과정

첫 번째 방식:
a의 ASCII = 97
b의 ASCII = 98
hash = (97 + 9831) mod m
두 번째 방식:
1단계: hash = (0 31 + 97) = 97
2단계: hash = (97 * 31 + 98) = 3105
최종: hash = 3105 mod m

실제 적용시의 특징

두 방식 모두 같은 문자열에 대해 다른 해시값을 생성할 수 있음
하지만 두 방식 모두 해시 함수의 기본 속성(같은 입력 → 같은 출력)을 만족
두 번째 방식이 구현이 더 간단하고 실수할 가능성이 적음

결론적으로,
두 번째 방식(polynomialHash)이 더 효율적이고 간단한 구현이지만, 두 방식 모두 문자열 해싱의 목적을 충분히 달성할 수 있습니다. 실제 사용시에는 두 번째 방식을 추천드립니다.