JavaScript로 문자열 배열에서 가장 긴 비공통 부분 수열(Longest Uncommon Subsequence) 찾기

부분 수열(Subsequence)이란?

먼저 용어부터 정리해 보겠습니다. 부분 수열(subsequence)이란 원래 시퀀스에서 일부 문자를 삭제하여 얻을 수 있는 시퀀스로, 남은 요소들의 순서는 그대로 유지됩니다. 예를 들어 "ace"는 "abcde"의 부분 수열입니다. 모든 문자열은 자기 자신의 부분 수열이며, 빈 문자열은 모든 문자열의 부분 수열입니다.

문제 정의

문자열 배열을 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열 안에서 가장 긴 비공통 부분 수열(longest uncommon subsequence)의 길이를 반환해야 합니다.

여기서 '비공통 부분 수열'이란, 배열 내 한 문자열의 부분 수열이면서 동시에 나머지 다른 문자열들의 부분 수열은 아닌 것을 의미합니다. 만약 비공통 부분 수열이 존재하지 않는다면 -1을 반환해야 합니다.

입출력 예시

예를 들어 함수에 다음 배열을 입력한다고 가정해 보겠습니다.

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

이 경우 출력은 다음과 같습니다.

const output = 3;

결과 설명: "aba", "cdc", "eae" 세 문자열은 서로의 부분 수열이 아니므로, 각 문자열 자체가 길이 3의 유효한 비공통 부분 수열이 됩니다. 따라서 최댓값인 3이 반환됩니다.

반면 입력이 ["aba", "aba"]처럼 완전히 동일한 문자열 두 개라면, 한쪽의 모든 부분 수열이 곧 상대방의 부분 수열이 되기 때문에 비공통 부분 수열이 존재하지 않아 -1을 반환하게 됩니다.

접근 방식

이 문제의 핵심 통찰은 의외로 단순합니다. 어떤 문자열 전체가 다른 모든 문자열의 부분 수열이 아니라면, 그 문자열 자체가 곧 해당 문자열이 가질 수 있는 가장 긴 비공통 부분 수열입니다. 문자열은 항상 자기 자신의 부분 수열이기 때문입니다.

따라서 다음과 같은 알고리즘으로 문제를 해결할 수 있습니다.

배열을 문자열 길이 기준으로 내림차순 정렬합니다.
각 문자열에 대해, 나머지 모든 문자열의 부분 수열인지 검사합니다.
어떤 문자열도 자신을 부분 수열로 포함하지 않는다면, 즉시 그 문자열의 길이를 반환합니다.
모든 문자열이 검사에 실패하면 -1을 반환합니다.

길이가 같은 두 문자열은 서로 다른 이상 한쪽이 다른 쪽의 부분 수열일 수 없습니다. 또한 완전히 동일한 문자열이 여러 개 존재한다면 그 문자열은 절대 답이 될 수 없다는 점도 기억해 두면 좋습니다.

구현 코드

// s가 t의 부분 수열인지 확인하는 헬퍼 함수
const isSubsequence = (s, t) => {
   let i = 0;
   for(let j = 0; j < t.length && i < s.length; j++){
      if(s[i] === t[j]) i++;
   }
   return i === s.length;
};

const longestUncommon = (strs) => {
   // 길이가 긴 순서대로 정렬
   const sorted = [...strs].sort((a, b) => b.length - a.length);
   for(let i = 0; i < sorted.length; i++){
      let isUncommon = true;
      for(let j = 0; j < sorted.length; j++){
         // 자기 자신을 제외한 다른 문자열의 부분 수열인지 검사
         if(i !== j && isSubsequence(sorted[i], sorted[j])){
            isUncommon = false;
            break;
         }
      }
      if(isUncommon) return sorted[i].length;
   }
   return -1;
};

const arr = ["aba", "cdc", "eae"];
console.log(longestUncommon(arr));

출력 결과

콘솔에는 다음과 같이 출력됩니다.

동작 원리 살펴보기

"aba"는 길이가 같은 "cdc", "eae"와 다른 문자열이므로 이들의 부분 수열이 될 수 없습니다. 따라서 첫 번째 검사에서 바로 조건을 만족하고 길이 3이 반환됩니다.

만약 배열이 ["aaa", "aa"]라면 "aa"는 "aaa"의 부분 수열이지만, "aaa"는 "aa"의 부분 수열이 아니므로 결과는 3이 됩니다. 반면 ["aaa", "aaa"]라면 모든 문자열이 다른 문자열의 부분 수열이므로 -1이 반환됩니다.

시간 복잡도

n개의 문자열 각각에 대해 다른 n-1개의 문자열과 부분 수열 여부를 검사하고, 각 검사는 O(L)(L은 문자열 길이)에 수행되므로 전체 시간 복잡도는 대략 O(n² × L)입니다. 문자열 개수와 길이가 크지 않은 일반적인 입력에서는 충분히 효율적으로 동작합니다.