자바스크립트로 문자열 배열에서 가장 긴 고유 부분 수열 찾기

문제 소개

문자열 배열을 입력받아, 배열에 포함된 문자열들 사이에서 가장 긴 고유 부분 수열(Longest Uncommon Subsequence)을 찾는 자바스크립트 함수를 작성해 보겠습니다.

여기서 말하는 '고유 부분 수열'이란 배열 내 특정 문자열의 부분 수열이면서, 동시에 나머지 다른 어떤 문자열의 부분 수열에도 해당하지 않는 수열을 의미합니다. 참고로 부분 수열(subsequence)은 원본 문자열에서 문자의 순서를 유지한 채 일부 문자를 삭제하여 만들어진 수열을 뜻합니다.

함수는 최종적으로 이 가장 긴 고유 부분 수열의 길이를 반환해야 합니다.

입력 예시

예를 들어 입력 배열이 다음과 같다고 가정해 봅시다.

const arr = ["aba", "cdc", "eae"];

세 문자열은 서로의 부분 수열이 아니므로, 가장 긴 고유 부분 수열의 길이는 3이 됩니다.

구현 코드

const arr = ["aba", "cdc", "eae"];
const findUncommonLength = (array = []) => {
    const seen = {};
    const arr = [];
    let max = −1;
    let index = −1;
    for(let i = 0; i < array.length; i++){
        seen[array[i]] = (seen[array[i]] || 0) + 1;
        if(seen[array[i]] > 1){
            if(max < array[i].length){
                max = array[i].length
                index = i;
            }
        }
    };
    if(index === −1) {
        array.forEach(el =>{
            if(el.length > max) max = el.length;
        })
        return max;
    };
    for(let i = 0; i < array.length; i++){
        if(seen[array[i]] === 1) arr.push(array[i]);
    };
    max = −1;
    for(let i = arr.length − 1; i >= 0; i−−){
        let l = arr[i];
        let d = 0;
        for(let j = 0; j < array[index].length; j++){
            if(array[index][j] === l[d]){
                d++;
            }
        }
        if(d === l.length){
            let temp = arr[i];
            arr[i] = arr[arr.length − 1];
            arr[arr.length − 1] = temp;
            arr.pop();
        }
    };
    arr.forEach(el =>{
        if(el.length > max) max = el.length;
    });
    return max;
};
console.log(findUncommonLength(arr));

코드 동작 방식

중복 여부 확인: seen 객체를 사용해 각 문자열의 등장 횟수를 기록합니다. 동일한 문자열이 두 번 이상 등장한다면, 그 문자열 자체는 고유 부분 수열이 될 수 없습니다. 서로가 서로의 부분 수열이 되어버리기 때문입니다.
모든 문자열이 유일한 경우: 중복된 문자열이 하나도 없다면(index === -1), 가장 긴 문자열이 곧 정답입니다. 그보다 긴 문자열이 존재하지 않으므로 다른 문자열의 부분 수열이 될 가능성이 전혀 없기 때문입니다.
후보 필터링: 중복된 문자열 중 가장 긴 것을 기준으로 삼고, 두 포인터 방식으로 순회하며 해당 문자열의 부분 수열에 포함되는 유일한 문자열들을 후보 목록에서 제거합니다.
결과 반환: 마지막으로 남은 후보 문자열들 중 가장 긴 것의 길이를 반환합니다.

실행 결과

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