JavaScript로 풀어보는 표현 단어(Expressive Words) 문제

문제 소개

사람들은 종종 감정을 더 강하게 드러내기 위해 글자를 반복해서 사용합니다. 예를 들어 "hello"는 "heeellooo"로, "hi"는 "hiiii"로 표현될 수 있습니다. 이렇게 만들어진 문자열에는 동일한 문자가 연속된 그룹들이 존재하는데, "heeellooo"의 경우 "h", "eee", "ll", "ooo"라는 네 개의 그룹으로 구성되어 있습니다.

문제 정의: Stretchy(늘어나는) 단어란?

주어진 문자열 S에 대해, 아래의 확장(extension) 연산을 원하는 만큼 적용했을 때 질의 단어(query word)를 S와 똑같이 만들 수 있다면, 그 단어를 stretchy하다고 합니다.

확장 연산: 특정 문자 c로 이루어진 그룹을 선택한 뒤, 같은 문자 c를 몇 개 추가하여 해당 그룹의 크기를 3 이상으로 만듭니다.

예를 들어 "hello"에서 "o" 그룹을 확장하면 "hellooo"를 얻을 수 있지만, "helloo"는 만들 수 없습니다. 그룹 "oo"의 크기가 3 미만이기 때문입니다. 마찬가지로 "ll" → "lllll"과 같은 확장을 추가로 적용하면 "helllllooo"를 만들 수 있습니다.

따라서 S = "helllllooo"일 때 질의 단어 "hello"는 다음 과정을 거쳐 S와 같아지므로 stretchy한 단어입니다.

query = "hello" → "hellooo" → "helllllooo" = S

요구 사항

질의 단어 목록이 주어졌을 때, 그중 stretchy한 단어의 개수를 반환해야 합니다.

입력 예시

const str = 'heeellooo';

질의 단어 목록은 다음과 같습니다.

const words = ["hello", "hi", "helo"];

이 경우 기대되는 출력은 다음과 같습니다.

const output = 1

세 단어 중 "hello"만 확장을 통해 "heeellooo"로 만들 수 있고, "hi"와 "helo"는 불가능하기 때문입니다.

풀이 코드

이 문제는 투 포인터(two pointer) 기법으로 효율적으로 해결할 수 있습니다. 문자열 S와 각 질의 단어를 앞에서부터 동시에 순회하면서, 같은 문자로 이루어진 그룹의 길이를 비교하는 방식입니다.

const str = 'heeellooo';
const words = ["hello", "hi", "helo"];
const extraWords = (str, words) => {
    let count = 0;
    for (let w of words) {
        let i = 0;
        let j = 0;
        for (; i < str.length && j < w.length && w[j] === str[i];) {
            let lenS = 1;
            let lenW = 1;
            for (; i+lenS < str.length && str[i+lenS] === str[i]; lenS++);
            for (; j+lenW < w.length && w[j+lenW] === w[j]; lenW++);
            if (lenS < lenW || lenS > lenW && lenS < 3) break;
            i += lenS;
            j += lenW;
        }
        if (i === str.length && j === w.length) {
            count++;
        }
    }
    return count;
}
console.log(extraWords(str, words));

코드 동작 원리

포인터 i는 문자열 S를, 포인터 j는 질의 단어 w를 가리킵니다.
두 위치의 문자가 같다면, 각 문자열에서 해당 문자가 연속된 그룹의 길이(lenS, lenW)를 셉니다.
S의 그룹이 질의 단어의 그룹보다 짧거나(lenS < lenW), 더 길더라도 크기가 3 미만이라면(lenS > lenW && lenS < 3) 해당 단어는 stretchy하지 않으므로 반복을 중단합니다.
조건을 통과하면 두 포인터를 각 그룹 길이만큼 앞으로 이동시켜 다음 그룹을 비교합니다.
모든 그룹 비교가 끝난 후 두 포인터가 각 문자열의 끝에 동시에 도달했다면, 해당 단어는 stretchy하므로 카운트를 증가시킵니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.