JavaScript로 문자열 배열에서 부분 문자열 조합 모두 찾는 방법

문제 정의

문자열 배열을 인수로 받아, 배열 안에 존재하는 모든 부분 문자열(substring)과 슈퍼스트링(superstring) 조합을 찾아 해당 요소들을 배열로 반환하는 JavaScript 함수를 작성해야 합니다.

예를 들어 다음과 같은 배열이 주어졌다고 가정해 보겠습니다.

const arr = ["abc", "abcd", "abcde", "xyz"];

이때 기대되는 출력 결과는 다음과 같습니다.

const output = ["abc", "abcd", "abcde"];

'xyz'는 다른 어떤 문자열과도 포함 관계가 없기 때문에 제외되고, 나머지 세 문자열은 'abc' ⊂ 'abcd' ⊂ 'abcde'처럼 서로 부분 문자열 관계를 이루고 있으므로 결과에 포함됩니다.

구현 코드

이 문제는 이중 반복문과 indexOf() 메서드를 활용하면 간단하게 해결할 수 있습니다.

const arr = ["abc", "abcd", "abcde", "xyz"];

const findStringCombinations = (arr = []) => {
    let i, j, res = {};
    for (i = 0; i < arr.length - 1; i++) {
        if (res[arr[i]]) {
            continue;
        };
        for (j = i + 1; j < arr.length; j++) {
            if (res[arr[j]]) {
                continue;
            }
            if (arr[i].indexOf(arr[j]) !== -1 || arr[j].indexOf(arr[i]) !== -1) {
                res[arr[i]] = true;
                res[arr[j]] = true;
            }
        };
    };
    const result = arr.filter(el => res[el]);
    return result;
};

console.log(findStringCombinations(arr));

실행 결과

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

[ 'abc', 'abcd', 'abcde' ]

코드 동작 원리

• 모든 쌍 비교: 바깥쪽 반복문(i)과 안쪽 반복문(j)을 조합해 배열 내 모든 문자열 쌍을 한 번씩 비교합니다.
• 포함 여부 판별: indexOf()의 반환값이 -1이 아니라면 한 문자열이 다른 문자열 안에 포함되어 있다는 뜻입니다. 두 방향(arr[i] 안에 arr[j]가 있는 경우, 또는 arr[j] 안에 arr[i]가 있는 경우)을 모두 검사합니다.
• 중복 검사 생략: res 객체에 이미 표시된 문자열은 continue로 건너뛰어 불필요한 비교를 줄입니다.
• 결과 반환: 마지막에는 filter()를 사용해 포함 관계가 확인된 문자열만 원래 배열의 순서 그대로 골라냅니다.

이중 반복문으로 모든 문자열 쌍을 비교하기 때문에 시간 복잡도는 O(n²) 수준이며, 여기에 각 비교에서 발생하는 문자열 검색 비용이 추가됩니다. 따라서 배열의 크기가 매우 큰 경우에는 성능 최적화를 함께 고려하는 것이 좋습니다.