문제 정의

두 개의 문자열 source와 target이 주어질 때, source가 target의 부분 수열(subsequence)인지 판별하라. 두 문자열은 모두 소문자 알파벳으로 구성된다.

부분 수열은 원본 문자열에서 일부 문자를 제거하되(0개도 가능), 남은 문자의 상대적 순서를 유지하여 만들 수 있는 문자열이다. 예를 들어 "ace"는 "abcde"의 부분 수열이지만 "aec"는 아니다.

확장 시나리오

target은 고정된 상태에서 수십억 개의 source 문자열(source₁, source₂, ..., sourceₖ, k ≥ 10⁹)에 대해 각각 부분 수열 여부를 판별해야 한다면?

기본 풀이: 투 포인터

소규모 데이터에 적합한 방식이다. source의 각 문자를 target에서 순차적으로 찾되, 이미 확인한 위치 이후만 탐색한다.

public boolean checkSubsequence(String source, String target) {
    if (source.length() > target.length()) return false;
    
    int srcIdx = 0, tgtIdx = 0;
    while (srcIdx < source.length() && tgtIdx < target.length()) {
        if (source.charAt(srcIdx) == target.charAt(tgtIdx)) {
            srcIdx++;  // 문자 일치 시 source 포인터 전진
        }
        tgtIdx++;      // 항상 target 포인터 전진
    }
    
    return srcIdx == source.length();  // source 전체 매칭 여부
}

대용량 최적화: 전처리 기반 탐색

확장 시나리오에서 target은 불변이므로, 한 번의 전처리로 O(1)에 가까운 질의가 가능하다.

핵심 아이디어

각 문자가 등장하는 위치를 미리 계산하여 저장한다. target = "abcabdd"일 때, 각 인덱스에서 각 문자가 다음에 등장하는 위치를 기록한다.

public class SubsequenceChecker {
    private int[][] nextPos;  // nextPos[c][i]: 인덱스 i 이후 문자 c가 처음 등장하는 위치
    
    public SubsequenceChecker(String target) {
        int len = target.length();
        nextPos = new int[26][len + 1];
        
        // 초기화: 존재하지 않음을 -1로 표시
        for (int c = 0; c < 26; c++) {
            nextPos[c][len] = -1;
        }
        
        // 역순 전처리: 뒤에서부터 채워나간다
        for (int c = 0; c < 26; c++) {
            for (int i = len - 1; i >= 0; i--) {
                if (target.charAt(i) - 'a' == c) {
                    nextPos[c][i] = i;           // 현재 위치에 해당 문자 존재
                } else {
                    nextPos[c][i] = nextPos[c][i + 1];  // 이후 위치에서의 결과 상속
                }
            }
        }
    }
    
    public boolean isSubsequence(String source) {
        int pos = 0;  // target에서 현재 검색 시작 위치
        for (int i = 0; i < source.length(); i++) {
            int ch = source.charAt(i) - 'a';
            if (pos >= nextPos[0].length - 1 || nextPos[ch][pos] == -1) {
                return false;  // 더 이상 해당 문자 없음
            }
            pos = nextPos[ch][pos] + 1;  // 다음 검색은 매칭된 위치 직후부터
        }
        return true;
    }
}

대안: 이진 탐색 기반 접근

각 문자의 등장 위치를 리스트로 저장하고, 이진 탐색으로 다음 위치를 찾는 방식이다.

public boolean binarySearchApproach(String source, String target) {
    if (source.length() > target.length()) return false;
    
    // 각 문자별 등장 인덱스 목록 구성
    List<Integer>[] charIndices = new ArrayList[26];
    for (int i = 0; i < target.length(); i++) {
        int idx = target.charAt(i) - 'a';
        if (charIndices[idx] == null) {
            charIndices[idx] = new ArrayList<>();
        }
        charIndices[idx].add(i);
    }
    
    int prevMatch = -1;
    for (int i = 0; i < source.length(); i++) {
        int ch = source.charAt(i) - 'a';
        List<Integer> indices = charIndices[ch];
        
        if (indices == null) return false;
        
        // prevMatch보다 큰 첫 번째 인덱스 탐색
        int found = lowerBound(indices, prevMatch + 1);
        if (found == indices.size()) return false;
        
        prevMatch = indices.get(found);
    }
    return true;
}

private int lowerBound(List<Integer> list, int minVal) {
    int lo = 0, hi = list.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (list.get(mid) < minVal) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

복잡도 비교

추가 최적화 고려사항

• DP 테이블의 문자 범위를 26에서 실제 등장 문자만으로 축소 (HashMap 활용)
• 비트마스크를 활용한 공간 절약 (소문자만 고려 시 32비트 정수로 위치 압축 가능)
• source 문자열의 길이가 target보다 긴 경우 즉시 종료