Is Subsequence — 투 포인터 `O(|s| + |t|)`로 부분 수열 판정

부분 수열인지 확인하기, 어떤 문제인가요?

LeetCode 392번 문제는 이렇게 주어집니다.

문자열 s와 t가 주어질 때, s가 t의 부분 수열(subsequence) 이면 true, 아니면 false를 반환합니다. 부분 수열은 문자를 몇 개 지우더라도 남은 문자의 상대적 순서가 유지되어야 합니다.

예시는 이렇습니다.

• s = "abc", t = "ahbgdc" → true
• s = "axc", t = "ahbgdc" → false

제약은 다음과 같습니다.

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• s, t는 소문자 영문으로만 구성

문제 끝에는 follow-up도 붙습니다.

• 같은 t에 대해 s1, s2, ..., sk처럼 아주 많은 질의가 들어오면 어떻게 바꿀 것인가

핵심은 s의 문자를 순서대로 소비할 수 있는가입니다. 이 글에서는 indexOf로 다음 문자를 찾는 방식부터, 투 포인터 O(|s| + |t|) 풀이, 그리고 follow-up용 전처리 + 이진 탐색까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

Phase 1. indexOf로 다음 문자를 순서대로 찾기

가장 먼저 떠올릴 수 있는 방법은 이렇습니다. s의 각 문자를 보면서, t 안에서 직전에 찾은 위치 뒤쪽에서 같은 문자를 찾습니다.

fun isSubsequence(s: String, t: String): Boolean {
    var from = 0

    for (ch in s) {
        val idx = t.indexOf(ch, from)
        if (idx == -1) return false
        from = idx + 1
    }
    return true
}

s = "abc", t = "ahbgdc"를 따라가 봅시다.

• 'a'를 from = 0부터 찾음 → idx = 0
• 'b'를 from = 1부터 찾음 → idx = 2
• 'c'를 from = 3부터 찾음 → idx = 5
• 모든 문자를 순서대로 찾았으므로 true

이 방식의 핵심은 항상 가장 이른 가능한 위치에 매칭한다는 점입니다. 부분 수열은 순서만 중요하므로, 더 앞에서 매칭할수록 뒤에 남는 선택지가 많아집니다. 따라서 현재 문자를 가능한 한 빨리 잡는 선택이 손해가 되지 않습니다.

시간 복잡도는 from이 뒤로만 움직이므로 전체적으로 O(|s| + |t|)로 볼 수 있습니다. 다만 실제 스캔이 indexOf 안에 숨어 있어서, 왜 한 번의 선형 스캔으로 끝나는지가 코드만 보고 바로 드러나지는 않습니다.

Phase 2. 투 포인터 — 스캔 원리를 코드에 그대로 드러내기

위 풀이를 직접 풀어 쓰면 투 포인터가 됩니다. 하나의 포인터 i는 s를, 다른 포인터 j는 t를 가리킵니다.

fun isSubsequence(s: String, t: String): Boolean {
    var i = 0
    var j = 0

    while (i < s.length && j < t.length) {
        if (s[i] == t[j]) {
            i++
        }
        j++
    }

    return i == s.length
}

분기는 단순합니다.

• s[i] == t[j]면 현재 문자를 매칭했으므로 i++, j++
• 다르면 t 쪽에서만 다음 문자를 보므로 j++

s = "axc", t = "ahbgdc"를 따라가 봅시다.

s: a x c
   ^
t: a h b g d c
   ^

• a == a → i = 1, j = 1
• x != h → j = 2
• x != b → j = 3
• x != g → j = 4
• x != d → j = 5
• x != c → j = 6 종료

i는 아직 1이므로, s를 끝까지 소비하지 못했습니다. 따라서 false입니다.

왜 이 그리디가 항상 맞나요?

현재 문자를 매칭할 수 있는 위치가 t 안에 여러 군데 있다면, 가장 앞의 위치를 잡는 것이 항상 유리합니다.

예를 들어 s[i]를 t의 두 위치 j1 < j2에서 모두 매칭할 수 있다고 합시다. j2를 선택해서 이후 문자를 모두 맞출 수 있었다면, j1을 선택한 경우에는 그보다 더 긴 suffix인 t[j1 + 1 ..]가 남습니다. 즉 뒤에 남는 공간이 더 많거나 같으므로, 더 나빠질 수 없습니다.

이 문제에서 투 포인터가 자연스러운 이유가 여기에 있습니다. 부분 수열은 "순서를 지키며 건너뛸 수 있느냐"만 묻기 때문에, t를 한 번 왼쪽에서 오른쪽으로 훑으면 충분합니다.

빈 문자열은 왜 항상 true인가요?

s가 빈 문자열이면 지울 문자가 없으므로 어떤 문자열의 부분 수열이기도 합니다. 위 코드에서는 처음부터 i == s.length가 성립하므로 자연스럽게 true가 반환됩니다.

시간 복잡도는 O(|s| + |t|), 공간 복잡도는 O(1)입니다.

Phase 3. follow-up — 같은 t에 대한 질의가 아주 많다면

문제의 follow-up은 관점이 조금 다릅니다. t는 고정이고, s만 계속 바뀌는 상황입니다.

이때 매 질의마다 t를 처음부터 끝까지 다시 훑으면, 질의 수 k가 매우 클 때 비용이 커집니다. 그래서 t를 한 번 전처리해 두고, 각 질의는 빠르게 처리하는 방식으로 바꾸는 것이 좋습니다.

핵심 아이디어는 문자별 등장 위치를 미리 저장하는 것입니다.

t = "ahbgdc"

'a' -> [0]
'b' -> [2]
'c' -> [5]
'd' -> [4]
'g' -> [3]
'h' -> [1]

이제 s의 각 문자에 대해, 직전에 선택한 인덱스보다 큰 위치 중 가장 왼쪽 것을 이진 탐색으로 찾으면 됩니다.

class SubsequenceChecker(t: String) {
    private val positions = Array(26) { mutableListOf<Int>() }

    init {
        for (i in t.indices) {
            positions[t[i] - 'a'].add(i)
        }
    }

    fun isSubsequence(s: String): Boolean {
        var prev = -1

        for (ch in s) {
            val list = positions[ch - 'a']
            val next = upperBound(list, prev)
            if (next == list.size) return false
            prev = list[next]
        }
        return true
    }

    private fun upperBound(list: List<Int>, target: Int): Int {
        var left = 0
        var right = list.size

        while (left < right) {
            val mid = (left + right) / 2
            if (list[mid] <= target) {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left
    }
}

s = "abc"를 다시 보겠습니다.

• prev = -1, 'a'의 위치 목록 [0]에서 -1보다 큰 첫 위치 → 0
• prev = 0, 'b'의 위치 목록 [2]에서 0보다 큰 첫 위치 → 2
• prev = 2, 'c'의 위치 목록 [5]에서 2보다 큰 첫 위치 → 5
• 끝까지 찾았으므로 true

반대로 s = "axc"라면 'x'의 위치 목록이 비어 있으므로 바로 false입니다.

언제 이 방식이 유리한가요?

한 번만 물어보는 상황에서는 Phase 2의 투 포인터가 가장 간단합니다. 하지만 같은 t에 대해 수많은 s를 검사해야 한다면:

• 전처리: O(|t|)
• 질의 1건당: O(|s| log |t|)

로 바뀝니다. t를 매번 다시 스캔하는 비용을 없앴기 때문에, 질의 수가 많을수록 전처리 비용을 회수하기 쉬워집니다.

참고: 이 문제는 s, t가 소문자 영문으로만 구성되므로 Array(26)으로 충분합니다. 문자 종류가 더 넓다면 Map<Char, MutableList<Int>>로 일반화하면 됩니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
indexOf 순차 탐색	`O(	s	+
투 포인터	`O(	s	+
위치 배열 + 이진 탐색	전처리 `O(	t	), 질의당 O(

마무리

1. 이 문제의 핵심은 s를 왼쪽부터 순서대로 소비할 수 있는지만 보면 된다는 점 — 부분 수열은 연속성이 아니라 순서만 요구합니다
2. 투 포인터가 정답인 이유는 "현재 문자를 가능한 한 앞에서 매칭하는 선택이 미래 선택지를 줄이지 않기 때문" — 더 앞에서 잡을수록 뒤에 남는 공간이 더 많습니다
3. 한 번만 검사할 때는 O(|s| + |t|) 투 포인터가 가장 간단하고 충분합니다 — 문제의 기본 해법은 여기서 끝납니다
4. follow-up처럼 같은 t에 대한 질의가 매우 많다면, t를 전처리하고 각 질의는 이진 탐색으로 처리하는 구조가 더 적합합니다 — "한 번 스캔" 최적화에서 "여러 번 질의" 최적화로 관점을 바꾸는 문제입니다