Two Pointers와 Sliding Window: 배열과 문자열 최적화 기법

1. 개요

배열이나 문자열을 순회하는데 brute-force 해법이 O(n²) 또는 O(n³)이 되는 문제에서 two pointers와 sliding window 기법을 사용하면 보통 시간 복잡도를 O(n)으로 낮출 수 있습니다. 이 글에서는 두 기법의 핵심 개념을 설명하고 구체적인 Java 예제를 제시합니다: 정렬된 배열에서의 two sum, palindrome 확인, 고정 크기 윈도우에서의 최대합, 반복 문자가 없는 가장 긴 부분 문자열. 이 글을 다 읽고 나면 패턴을 인식하고 유사한 많은 문제에 이 기법들을 적용할 수 있을 것입니다.

2. Two Pointers란 무엇인가

Two pointers는 두 개의 인덱스 변수(포인터)를 사용하여 자료 구조(보통은 정렬된 배열이나 문자열) 위에서 움직이며 중첩 순회를 피하는 기법입니다. 두 포인터는 다음과 같이 이동할 수 있습니다:

• 같은 방향 (fast/slow): 중복 요소 제거, 사이클 감지에 사용.
• 반대 방향 (양쪽 끝에서 left/right): 합이 target인 쌍 찾기, palindrome 확인에 사용.

2.1. 반대 방향 two pointers: 목표값 합을 갖는 쌍 찾기

고전적인 문제: 정렬된 배열이 주어졌을 때, 합이 target과 같은 두 수를 찾아야 합니다.

public class TwoSumSorted {

    public int[] findPair(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{numbers[left], numbers[right]};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
}

설명:

• left는 배열의 처음에서 시작하고, right는 배열의 끝에서 시작합니다.
• sum < target이면, left 쪽의 수가 너무 작으므로 left를 증가시켜 더 큰 수를 선택합니다.
• sum > target이면, right 쪽의 수가 너무 크므로 right를 감소시킵니다.
• 루프는 최대 n번 실행되는데, 매번 left 또는 right 중 하나가 한 칸씩 이동하므로 중첩 순회의 O(n²) 대신 O(n) 시간 복잡도가 됩니다.

JUnit 5 + AssertJ로 테스트:

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.10.2</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.25.3</version>
    <scope>test</scope>
</dependency>

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class TwoSumSortedTest {

    private final TwoSumSorted twoSum = new TwoSumSorted();

    @Test
    void shouldFindPairWhenSumMatchesTarget() {
        int[] numbers = {1, 3, 5, 8, 11};

        int[] result = twoSum.findPair(numbers, 13);

        assertThat(result).containsExactly(5, 8);
    }
}

주의: 이 기법은 배열이 정렬되어 있어야 합니다. 배열이 정렬되지 않았다면 먼저 정렬해야 하거나 (O(n log n)) HashMap을 사용하여 정렬 없이 O(n)을 유지할 수 있습니다.

2.2. Palindrome 확인을 위한 two pointers

public class PalindromeChecker {

    public boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

두 포인터는 문자열의 양쪽 끝에서 시작하여 문자를 비교하며 가운데로 나아갑니다. 다른 문자 쌍을 만나면 즉시 false를 반환하며, 전체를 순회할 필요가 없습니다. 이 기법이 문자열을 뒤집고 비교하는 방식(reverse().equals())보다 빠른 이유는 중간에 StringBuilder 객체를 생성하지 않기 때문입니다.

3. Sliding Window란 무엇인가

Sliding window는 two pointers의 변형으로, 연속 부분 수열(subarray/substring)과 관련된 문제에 적용됩니다. 각 시작 위치마다 처음부터 다시 계산하는 대신, [left, right] “윈도우”를 유지하고 윈도우가 이동할 때마다 점진적으로 업데이트하여 이전에 계산한 결과를 재사용합니다.

두 가지 유형이 있습니다:

• Fixed-size window: 윈도우 크기가 고정됨 (예: k개 요소)
• Variable-size window: 문제의 조건에 따라 윈도우 크기가 변함

3.1. Fixed-size window: 크기 k인 최대 부분합

public class MaxSumSubarray {

    public int maxSum(int[] numbers, int windowSize) {
        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += numbers[i];
        }

        int maxSum = windowSum;
        for (int right = windowSize; right < numbers.length; right++) {
            windowSum += numbers[right] - numbers[right - windowSize];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

설명:

• 첫 번째 루프는 첫 번째 윈도우의 합을 계산합니다 (인덱스 0부터 windowSize - 1까지).
• 그 다음부터는 윈도우를 한 단계씩 오른쪽으로 이동할 때마다, 새로운 요소를 더하고(numbers[right]), 윈도우를 벗어난 요소를 빼줍니다(numbers[right - windowSize]).
• 이렇게 하면 각 단계에 O(1)만 걸리며, 합을 다시 계산하는 O(k) 대신 전체 시간 복잡도가 O(n)이 됩니다.

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class MaxSumSubarrayTest {

    private final MaxSumSubarray solver = new MaxSumSubarray();

    @Test
    void shouldReturnMaxSumOfWindowSizeThree() {
        int[] numbers = {2, 1, 5, 1, 3, 2};

        int result = solver.maxSum(numbers, 3);

        assertThat(result).isEqualTo(9); // 윈도우 [5, 1, 3]
    }
}

3.2. Variable-size window: 반복 문자가 없는 가장 긴 부분 문자열

이 문제에서는 ’반복 문자가 없다’는 조건에 따라 윈도우가 확장하고 축소됩니다.

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public int lengthOfLongestSubstring(String text) {
        Map<Character, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < text.length(); right++) {
            char current = text.charAt(right);
            if (lastSeenIndex.containsKey(current) && lastSeenIndex.get(current) >= left) {
                left = lastSeenIndex.get(current) + 1;
            }
            lastSeenIndex.put(current, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

설명:

• right는 항상 앞으로 이동하여 윈도우를 확장하고, left는 현재 윈도우 내에 반복되는 문자가 있을 때만 점프합니다.
• lastSeenIndex는 각 문자의 가장 최근 위치를 저장하므로 left가 어디로 이동해야 하는지 알 수 있습니다.
• lastSeenIndex.get(current) >= left 조건은 문자가 현재 윈도우 내에 있을 때만 ’반복’으로 간주하여 left가 실수로 뒤로 이동하지 않도록 보장합니다.
• 각 문자는 right에서 정확히 한 번씩 처리되므로 전체 시간 복잡도는 O(n)입니다.

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class LongestUniqueSubstringTest {

    private final LongestUniqueSubstring solver = new LongestUniqueSubstring();

    @Test
    void shouldReturnLengthOfLongestUniqueSubstring() {
        int result = solver.lengthOfLongestSubstring("abcabcbb");

        assertThat(result).isEqualTo(3); // "abc"
    }

    @Test
    void shouldHandleAllSameCharacters() {
        int result = solver.lengthOfLongestSubstring("bbbbb");

        assertThat(result).isEqualTo(1);
    }
}

"abcabcbb"을 수동으로 디버그할 때의 출력:

right=0 'a' -> window="a"    length=1
right=1 'b' -> window="ab"   length=2
right=2 'c' -> window="abc"  length=3
right=3 'a' -> 반복, left=1 -> window="bca" length=3
right=4 'b' -> 반복, left=2 -> window="cab" length=3
...
maxLength = 3

4. 기법 비교 및 언제 각 기법을 사용할지

상황	적절한 기법
정렬된 배열에서 합 조건을 만족하는 쌍/삼중쌍 찾기	반대 방향 two pointers
대칭성 확인(Palindrome), 배열을 제자리에서 뒤집기	반대 방향 two pointers
정렬된 배열에서 중복 요소 제거	같은 방향 two pointers (fast/slow)
크기가 고정된 부분배열/부분 문자열	Sliding window (크기 고정)
동적 조건을 만족하는 부분배열/부분 문자열 (반복 없음, 합 ≤ target…)	Sliding window (크기 변수)

공통점: 두 기법 모두 이미 처리한 부분을 다시 계산하는 것을 피하며, 포인터/윈도우가 이동할 때 상태(sum, set, map)를 유지함으로써 O(n²)에서 O(n)으로 복잡도를 낮춥니다.

5. 자주 나타나는 실수

• left < right 종료 조건을 잊음: 무한 루프를 야기하거나 left == right일 때 한 요소와 자기 자신을 비교할 수 있습니다.
• 미정렬 배열에 two pointers를 적용하면서 먼저 정렬하는 것을 잊음 — 포인터 증감 로직이 배열의 단조성을 기반으로 하므로 결과가 완전히 잘못됩니다.
• Sliding window에서 left가 이동할 때 상태 업데이트를 잊음: 예를 들어 HashMap/sum에서 오래된 요소를 제거하는 것을 잊으면 윈도우가 더 이상 속하지 않는 데이터를 ’기억’하게 됩니다.
• 윈도우 확장/축소 조건을 혼동함: variable-size window에서는 어떤 조건이 right를 이동시키고 어떤 조건이 left를 이동시키는지 명확히 해야 합니다. 반대로 하면 윈도우가 제대로 축소되지 않습니다.

주의: 이 두 기법은 문제가 연속하지 않은 모든 부분 집합을 고려해야 할 때(예: subset sum) 적합하지 않습니다. 이런 경우에는 backtracking이나 dynamic programming이 필요하지, sliding window가 아닙니다.

6. 결론

Two pointers와 sliding window는 배열/문자열 문제를 선형 시간 복잡도로 해결하기 위한 두 가지 기본 도구입니다. 패턴을 인식할 수 있다면 — 정렬된 배열에서 쌍을 찾거나 연속 부분배열/부분 문자열을 최적화해야 하는 경우 — 올바른 기법을 선택하고 위의 예제처럼 간단하고 테스트하기 쉬운 코드를 작성할 수 있습니다. 연습할 때는 코드를 작성하기 전에 각 단계별로 left/right 상태를 직접 그려보고 불변식을 명확히 이해해야 합니다.