JavaScript로 문자열에서 만들 수 있는 가장 긴 단어 찾기

문제 정의

영어 알파벳으로 구성된 임의의 문자열 str을 첫 번째 인수로, 문자열 배열 arr을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.

함수의 목표는 문자열 str에서 일부 문자를 삭제해가며, 배열 arr에도 존재하는 단어 중 가장 긴 것을 찾아내는 것입니다. 함수는 형성 가능한 가장 긴 문자열을 반환해야 합니다.

만약 조건을 만족하는 문자열이 하나도 없다면 빈 문자열('')을 반환하면 됩니다.

입력 예시

const str = 'sdgfdfghdjh';
const arr = ['sdf', 'fghj', 'gfdfg', 'absc', 'a', 'hasl'];

출력 예시

const output = 'gfdfg';

출력 설명

배열의 첫 번째와 두 번째 요소 역시 문자열에서 문자를 삭제하여 만들 수 있지만, 'gfdfg'가 문자열 str로부터 만들 수 있는 가장 긴 단어(길이 5)이기 때문에 이것이 정답입니다.

구현 코드

const str = 'sdgfdfghdjh';
const arr = ['sdf', 'fghj', 'gfdfg', 'absc', 'a', 'hasl'];

const findLongestWord = (str = '', arr = []) => {
    // 길이 내림차순으로 정렬하되, 길이가 같으면 사전순으로 정렬
    arr.sort((a, b) => {
        if (a.length !== b.length) {
            return b.length - a.length;
        };
        return a.localeCompare(b);
    });
    for(const word of arr){
        let index = -1;
        for(const char of word){
            index = str.indexOf(char, index + 1);
            if(index < 0){
                break;
            };
        };
        if (index >= 0){
            return word;
        };
    };
    return '';
};
console.log(findLongestWord(str, arr));

코드 설명

이 코드의 동작 과정은 다음과 같습니다.

먼저 배열 arr을 길이 기준 내림차순으로 정렬하고, 길이가 같은 경우에는 사전순(lexical order)으로 정렬합니다.
정렬된 배열의 각 단어를 순회하면서, 해당 단어의 모든 문자가 문자열 str에 순서대로 포함되어 있는지 indexOf()를 활용해 확인합니다. 중간에 하나라도 매칭되지 않으면 즉시 다음 단어로 넘어갑니다.
단어의 모든 문자가 성공적으로 매칭되면, 그 단어를 바로 반환합니다.

사전 역할을 하는 배열을 미리 정렬해 두었기 때문에, 처음으로 매칭에 성공한 단어가 곧 가장 긴(그리고 사전순으로 앞선) 정답임을 보장할 수 있습니다. 덕분에 모든 후보를 검사할 필요 없이 효율적으로 답을 찾을 수 있습니다.

실행 결과

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

gfdfg