[Javascript] 문자열 해싱을 이용한 검색 함수 만들기

 

문제

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

제약 조건

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

입출력의 예

stringList	queryList	return
["apple", "banana", "cherry"]	["banana", "kiwi", " melon", "apple"]	[True, false, false, True]

 

나의 풀이

• 시간복잡도: O(N + M) (stringList: N, queryList: M)

function solution(stringList, queryList) {
    const m = 1000000007;
    const p = 31;

    // 해시 함수
    function hash(s) {
        let hashValue = 0;
        let p_pow = 1;
        for (let i = 0; i < s.length; i++) {
            hashValue = (hashValue + (s.charCodeAt(i) - 'a'.charCodeAt(0) + 1) * p_pow) % m;
            p_pow = (p_pow * p) % m;
        }
        return hashValue;
    }

    // stringList의 모든 문자열을 해시하여 저장
    const hashList = new Set();
    for (const s of stringList) {
        hashSet.add(hash(s));
    }

    // queryList의 각 문자열에 대해 검사
    const result = [];
    for (const query of queryList) {
        result.push(hashSet.has(hash(query)));
    }

    return result;
}

stringList의 모든 문자열을 해시하여 저장한 후, queryList의 각 문자열에 대해 해당 해시가 존재하는지 확인합니다.

 

다른 풀이

• 시간복잡도: O(N + M) (stringList: N, queryList: M)

// ➊ 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) {
  // ➋ stringList의 각 문자열에 대해 다항 해시값을 계산
  const hashList = stringList.map((str) => polynomialHash(str));

  // ➌ 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;
}

 

---

Reference

코딩테스트 합격자 되기: 자바스크립트 편