JavaScript 투 포인터 알고리즘으로 문자열 부분 수열(Subsequence) 여부 확인하기

문제 개요

두 개의 문자열 str1과 str2가 주어졌을 때, str1이 str2의 부분 수열(subsequence)인지 판별하는 함수를 작성해야 합니다.

여기서 부분 수열이란 원본 문자열에서 일부 문자(0개일 수도 있음)를 삭제하더라도 남은 문자들의 상대적인 순서는 그대로 유지된 채 만들어지는 새로운 문자열을 의미합니다.

예를 들어, "ace"는 "abcde"에서 b와 d를 제거한 것이므로 부분 수열이 맞지만, "aec"는 원본에서의 문자 순서가 뒤바뀌었기 때문에 부분 수열이 아닙니다.

풀이 접근 방식

이 문제는 투 포인터(two pointer) 기법으로 효율적으로 해결할 수 있습니다.

첫 번째 포인터 i는 str1을, 두 번째 포인터 j는 str2를 각각 가리킵니다. 두 위치의 문자가 일치하면 i를 증가시키고, j는 매 반복마다 항상 증가시켜 str2를 단 한 번만 순회합니다. 만약 j가 str2의 끝에 도달했는데도 str1의 모든 문자를 찾지 못했다면 false를 반환하고, 반복문이 정상적으로 종료되었다면 모든 문자를 순서대로 찾은 것이므로 true를 반환합니다.

예제 코드

const str1 = 'ace';
const str2 = 'abcde';
const isSubsequence = (str1, str2) => {
    let i = 0;
    let j = 0;
    while(i < str1.length){
        if(j === str2.length){
            return false;
        }
        if(str1[i] === str2[j]){
            i++;
        }
        j++;
    };
    return true;
};
console.log(isSubsequence(str1, str2));

실행 결과

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

true

복잡도 분석

이 알고리즘은 문자열 str2를 한 번만 순회하므로 시간 복잡도는 O(n)입니다(n은 str2의 길이). 또한 추가적인 메모리를 사용하지 않기 때문에 공간 복잡도 역시 O(1)로 매우 효율적입니다.