[프로그래머스] 가사 검색 - 자바스크립트

문제

코딩테스트 연습 - 가사 검색

이진탐색으로 풀기 위해서 많은 시간을 소요했고, 결국 풀어서 포스팅하게 되었다.
다소 로직이 더러울 수 있고 더 효과적인 방법이 있을 수 있으니, "이렇게도 정답은 나오는구나" 정도로 보시길 바랍니다.

---

코드

    function solution(words, queries) {
  const answer = [];
  const wordsObj = {};
  const reverseWordsObj = {};

  function findQuestion(query, start, end) {
    let result = -1;

    while (start <= end) {
      const mid = Math.floor((start + end) / 2);

      if (mid === 0) {
        if (query[mid] === '?') result = 0;
        else result = 1;
        break;
      }

      if (query[mid] === '?') {
        if (query[mid - 1] !== '?') {
          result = mid;
          break;
        } else {
          end = mid - 1;
        }
      } else {
        start = mid + 1;
      }
    }

    return result;
  }

  function findFirstWordIdx(wordArr, start, end, compareStr, questionIdx) {
    let result = -1;

    if (start === end) {
      if (wordArr[0].slice(0, questionIdx) === compareStr) return 0;
      return result;
    }

    while (start <= end) {
      const mid = Math.floor((start + end) / 2);
      const midStr = wordArr[mid].slice(0, questionIdx);

      if (mid === 0) {
        if (midStr === compareStr) {
          result = 0;
        } else if (wordArr[mid + 1].slice(0, questionIdx) === compareStr) {
          result = 1;
        }
        break;
      }

      const prevStr = wordArr[mid - 1].slice(0, questionIdx);

      if (midStr === compareStr) {
        if (prevStr !== compareStr) {
          result = mid;
          break;
        } else {
          end = mid - 1;
        }
      } else if (midStr > compareStr) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }
    return result;
  }

  function findLastWordIdx(wordArr, start, end, compareStr, questionIdx) {
    let result = end;

    while (start <= end) {
      const mid = Math.floor((start + end) / 2);
      const midStr = wordArr[mid].slice(0, questionIdx);

      if (mid === wordArr.length - 1) {
        result = mid;
        break;
      }

      const nextStr = wordArr[mid + 1].slice(0, questionIdx);

      if (midStr === compareStr) {
        if (nextStr !== compareStr) {
          result = mid;
          break;
        } else start = mid + 1;
      } else if (midStr > compareStr) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }

    return result;
  }

  for (let word of words) {
    const len = word.length;
    const reverseWord = word.split('').reverse().join('');

    if (!wordsObj[len]) {
      wordsObj[len] = [word];
      reverseWordsObj[len] = [reverseWord];
    } else {
      wordsObj[len].push(word);
      reverseWordsObj[len].push(reverseWord);
    }
  }

  function ascendSort(obj) {
    Object.values(obj).forEach((arr) => arr.sort());
  }

  ascendSort(wordsObj);
  ascendSort(reverseWordsObj);

  for (let query of queries) {
    const len = query.length;
    const isFrontQuestion = query[0] === '?';
    const isAllQuestion = query[0] === '?' && query[len - 1] === '?';

    if (isAllQuestion) {
      answer.push(wordsObj[len] ? wordsObj[len].length : 0);
      continue;
    }

    if (!wordsObj[len]) {
      answer.push(0);
      continue;
    }

    const targetQuery = isFrontQuestion
      ? query.split('').reverse().join('')
      : query;

    const questionIdx = findQuestion(targetQuery, 0, targetQuery.length - 1);

    const compareStr = targetQuery.slice(0, questionIdx);
    const targetWords = isFrontQuestion ? reverseWordsObj[len] : wordsObj[len];
    const endIdx = targetWords.length - 1;
    const args = [targetWords, 0, endIdx, compareStr, questionIdx];

    const firstIdx = findFirstWordIdx(...args);
    const lastIdx = findLastWordIdx(...args);

    answer.push(firstIdx === -1 ? 0 : lastIdx - firstIdx + 1);
  }

  return answer;
}

풀이

문제의 조건을 먼저 살펴본다.

 

가사 단어 제한사항

단어의 배열 words의 크기는 2 <= words.length <= 100,000 이다.
각 단어의 길이는 1 <= word.length <= 10,000 이다.
빈 문자열은 주어지지 않으며, 각 단어는 모두 알파벳 소문자로 구성되고 단어는 중복되지 않는다.
전체 단어의 길이의 합은 2 <= all <= 1,000,000 이다.

 

검색 키워드 제한사항

키워드의 배열, 각 키워드의 크기는 위의 단어와 동일하다.
키워드는 중복 가능하며 알파벳 소문자와 ? 문자로 구성된다.
문자 ?를 반드시 1개 이상 포함하며, 접두사 혹은 접미사 형태이다.( = ???abc abc??? 형태)
그리하여 a?bc abc ?abc?? 등은 불가능하다.

검색 키워드에서 ? 문자는 모든 문자에 매칭될 수 있으며, 각 키워드마다 매칭되는 가사 단어의 수를 반환해야 한다.

 

 

 

코드의 풀이 방향은 다음과 같다.

(열심히 한시간 넘게 작성했던 부분들이 포스팅을 하고 나니 열심히 설명한 부분만 다 날라갔다. 왜 그러는지 모르겠다.)

 

원래 조금 더 자세한 내용을 적었었지만.. 시행착오를 건너뛰고 내가 생각한 풀이 방향만을 설명하겠다.

 

1. 단어 배열words에서 word의 크기별로 분리한다. 이 때 기존 단어의 배열과 뒤집은 단어의 배열을 만들어준다.

2. 1에서 구한 모든 배열을 오름차순 정렬한다.(=키워드와 매칭되는 첫 인덱스와 마지막 인덱스를 구할 것이다.)

3. 키워드 배열 queries를 순회하면서 각 키워드들에 대한 매칭 수를 구한다.

    3-1. 키워드가 abc?? 형태라면 그대로 둔다.

    3-2. 키워드가 ??abc 형태라면 뒤집어준다. (이것 때문에 1에서 뒤집은 배열을 만들어줬고, 뒤집지 않으면 함수가 더 많아지고 복잡해질 것.)

    3-3. 키워드가 ????? 형태라면 키워드 길이와 길이가 같은 단어의 수가 매칭수이며, 단어가 없다면 0을 매칭한다.

    3-4. 키워드 길이와 동일한 길이의 단어들이 없다면, 0을 매칭한다.

    3-5. 키워드에서 ?이 등장하는 인덱스를 구한다. 이 인덱스를 구하면 첫번째 인덱스부터 해당 인덱스 전까지가 알파벳키워드에 해당한다.

    3-6. 탐색할 단어배열을 구한다. 키워드가 abc?? 형태였으면 기존단어의 배열, ??abc 형태였으면 뒤집은 단어의 배열이다.

    3-7. 단어 배열에서 이진탐색을 통해 키워드와 매칭된 단어가 출현하는 첫번째 인덱스와 마지막 인덱스를 구한다.

    3-8. 첫번째 인덱스(findFirstWordIdx함수) 결과가 -1이면, 키워드가 존재하지 않으므로 0을 더해주고, 존재한다면 매칭 개수를 더한다.

 

findQuestion, findFirstWordIdx, findLastWordIdx 3가지 함수 모두 이진탐색을 수행하는 함수이다.

그리고 여러 탈출조건을 고려하느라 함수가 조금 복잡해진 감도 있는 듯 하다.

 

다른분들의 코드를 찾아보니, Trie 자료구조로 구하는 방법도 있었고 abc??를 abcaa abczz 문자열로 나눠 구하는 방법도 있었으니

다양한 방법도 찾아보면 좋을 것 같다.