JavaScript로 공통 문자가 없는 두 단어의 최대 길이 곱 구하기

문제 설명

소문자 알파벳으로만 이루어진 문자열 배열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 배열에서 서로 공통된 문자를 하나도 포함하지 않는 두 문자열을 찾아야 하며, 그중 두 문자열 길이의 곱이 최대가 되는 조합을 선택해야 합니다. 그런 다음 해당 길이 곱을 반환하고, 만약 조건을 만족하는 두 문자열이 존재하지 않는다면 0을 반환하면 됩니다.

예시

함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

const arr = ["karl", "n", "the", "car", "mint", "alpha"];

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

const output = 20;

출력 설명

'mint'와 'alpha'는 공통 문자가 전혀 없으며, 길이는 각각 4와 5이므로 두 길이의 곱은 4 × 5 = 20이 됩니다. 다른 모든 조합은 공통 문자를 포함하거나 더 작은 곱을 가지므로, 정답은 20입니다.

접근 방식: 비트마스크(Bitmask)

두 문자열 사이에 공통 문자가 있는지 확인하는 가장 효율적인 방법 중 하나는 비트마스크를 활용하는 것입니다. 영어 알파벳은 총 26개이므로, 각 단어를 26비트 크기의 정수로 표현할 수 있습니다.

단어의 각 문자에 대해 charCodeAt(i) - 97을 계산하여 해당 알파벳의 비트 위치(a = 0, b = 1, ...)를 구합니다.
OR(|) 연산으로 각 비트를 누적하여 단어 전체의 문자 집합을 하나의 정수로 압축합니다.
두 단어의 비트마스크를 AND(&) 연산했을 때 결과가 0이라면, 두 단어는 공통 문자가 없다는 뜻입니다.

이렇게 하면 문자열을 직접 비교하는 것보다 훨씬 빠르게 공통 문자 여부를 판별할 수 있습니다.

예제 코드

이 로직을 구현한 코드는 다음과 같습니다.

const arr = ["karl", "n", "the", "car", "mint", "alpha"];

const maxLengthProduct = (arr = []) => {
    const array = [];
    // 각 단어를 26비트 비트마스크로 변환
    arr.forEach(str => {
        let curr = 0;
        for(let i = 0; i < str.length; i++){
            curr |= 1 << (str.charCodeAt(i) - 97);
        };
        array.push(curr);
    });
    let res = 0;
    // 모든 쌍을 비교하여 공통 문자가 없는 조합의 최대 길이 곱 계산
    for(let i = 0 ; i < array.length; i++) {
        for(let j = i + 1; j < array.length ; j++) {
            if((array[i] & array[j]) === 0) {
                res = Math.max(res, arr[i].length * arr[j].length);
            }
        }
    }
    return res;
};

console.log(maxLengthProduct(arr));

복잡도 분석

시간 복잡도: 비트마스크 생성에 O(n × L)(n은 단어 개수, L은 평균 단어 길이), 모든 쌍 비교에 O(n²)이 소요됩니다.
공간 복잡도: 각 단어의 비트마스크를 저장하기 위해 O(n)의 추가 공간이 필요합니다.

출력 결과

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