문자열 재정렬 없이 한 문자열에서 문자를 삭제해 다른 문자열을 만들 수 있는지 확인하는 방법 - JavaScript

두 개의 문자열 str1과 str2를 각각 첫 번째, 두 번째 인수로 받는 자바스크립트 함수를 작성해야 합니다.

이 함수는 어떤 문자열도 재정렬하지 않은 상태에서 str1의 일부 문자를 삭제하여 str2를 만들 수 있는지 판단해야 합니다.

예시

예를 들어 두 문자열이 다음과 같다고 가정해 보겠습니다.

const str1 = 'sjkfampeflef';
const str2 = 'sample';

이때 출력값은 true가 되어야 합니다. str1에서 몇 개의 문자만 제거하면 문자 순서를 바꾸지 않고도 str2인 'sample'을 얻을 수 있기 때문입니다.

코드 구현

다음은 이 문제를 해결하는 코드입니다.

const str1 = 'sjkfampeflef';
const str2 = 'sample';
const checkConvertibility = (str1 = '', str2 = '') => {
    if(!str1 || !str2){
        return false;
    };
    const strArr1 = str1.split('');
    const strArr2 = str2.split('');
    const shorter = strArr1.length < strArr2.length ? strArr1 : strArr2;
    const longer = strArr1.length < strArr2.length ? strArr2 : strArr1;
    for(let i = 0; i < shorter.length; i++){
        const el = shorter[i];
        const index = longer.indexOf(el);
        if(index !== -1){
            longer.splice(index, 1);
            continue;
        };
        return false;
    };
    return true;
};
console.log(checkConvertibility(str1, str2));

출력 결과

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

true

동작 원리

이 코드는 먼저 두 문자열을 문자 배열로 분리한 뒤, 더 짧은 문자열의 각 문자가 더 긴 문자열 배열에 존재하는지 확인합니다. 문자가 발견되면 해당 문자를 배열에서 제거(splice)하여 같은 문자를 중복해서 사용하지 않도록 처리하고, 하나라도 찾지 못하면 즉시 false를 반환합니다.

참고: 순서까지 정확하게 검사하려면?

위 코드는 문자의 종류와 개수만 비교하기 때문에 문자의 순서까지는 검증하지 못한다는 한계가 있습니다. 예를 들어 str1이 'elmpsa'라면 실제로는 재정렬 없이 'sample'을 만들 수 없음에도 불구하고 위 함수는 true를 반환합니다.

"재정렬 금지" 조건을 엄격하게 지키려면 str2가 str1의 부분 수열(subsequence)인지 확인하는 투 포인터 방식이 더 적합합니다.

const isSubsequence = (str1 = '', str2 = '') => {
    if(!str1 || !str2){
        return false;
    };
    let i = 0; // str1 포인터
    let j = 0; // str2 포인터
    while(i < str1.length && j < str2.length){
        if(str1[i] === str2[j]){
            j++;
        }
        i++;
    };
    return j === str2.length;
};
console.log(isSubsequence('sjkfampeflef', 'sample')); // true

이 방식은 두 문자열을 앞에서부터 한 번씩만 순회하므로 시간 복잡도가 O(n)으로 효율적이며, 별도의 배열을 생성하지 않기 때문에 메모리 사용 측면에서도 유리합니다.