투 포인터: 단조성을 근거로 후보 쌍을 한 번에 버리는 Java 패턴

투 포인터는 변수 두 개를 선언하는 기법이 아니다. 한쪽 경계를 움직일 때 제거되는 후보에 정답이 없다는 단조성이 있어야 한다. 대표 예제는 오름차순 배열에서 합이 target인 서로 다른 두 index를 찾는 문제다.

1. 문제 계약과 전제

입력은 오름차순 int[] sorted와 long target이다. pair가 있으면 index 두 개를 오름차순으로 반환하고, 없으면 빈 배열이다. 같은 index를 두 번 쓸 수 없으므로 loop 조건은 left < right다. 중복 값은 허용한다. null은 계약 위반이다.

정렬은 장식이 아니다. sum < target일 때 가장 작은 값인 sorted[left]를 더 큰 값으로 바꿔야 합을 키울 수 있다는 근거다. 정렬되지 않으면 left를 증가시킨 뒤 합이 어느 방향으로 변할지 알 수 없다.

2. brute force에서 제거 규칙을 찾는다

모든 쌍을 보면 $n(n-1)/2$개다. 정렬 배열 [1,2,4,7,11], target 9를 추적한다.

합이 너무 크면 현재 right와 더 큰 left를 조합해도 합은 더 작아지지 않으므로 right를 포함한 남은 후보는 모두 탈락한다. 합이 작으면 현재 left와 더 작은 right를 조합해도 합은 더 커지지 않으므로 left 후보를 버릴 수 있다.

3. loop 불변식과 정당성

불변식: 각 반복 시작 시 아직 가능한 모든 정답 쌍은 rectangle left <= i < j <= right 안에 있다.

• 초기에는 전체 index 쌍이 rectangle 안에 있다.
• 합이 작을 때 left를 포함한 어떤 쌍도 target에 도달하지 못하므로 left를 버려도 정답이 남는다.
• 합이 클 때 right를 포함한 어떤 쌍도 target 이하로 내려가지 못하므로 right를 버려도 정답이 남는다.
• 일치하면 계약을 만족하는 서로 다른 두 index다.
• left==right로 끝나면 가능한 서로 다른 쌍이 없으므로 빈 결과가 맞다.

답이 없는 예시에서도 제거 근거를 확인한다

정렬 배열 [-4,-1,2,5,9]에서 target 20을 찾으면 모든 합이 작다. 알고리즘은 left를 0에서 3까지 이동한 뒤 left==right로 종료한다. “못 찾았다”는 결론은 우연히 loop가 끝났기 때문이 아니라, 각 단계에서 현재 left를 포함하는 가장 큰 합조차 target보다 작아 그 left의 모든 쌍을 안전하게 제거했기 때문이다.

여기서 음수 값 자체는 문제가 아니다. 배열이 오름차순이면 left를 오른쪽으로 옮길 때 값이 작아지지 않는다는 단조성이 유지된다. 반대로 양수만 있어도 입력이 [9,1,5,2]처럼 정렬되지 않았다면 같은 제거는 정당하지 않다. 투 포인터 적용 여부를 “음수 포함” 같은 표면 조건이 아니라 이동 후 비교값의 방향이 보장되는가로 판단해야 한다.

실행 재현

아래 코드는 설명용 조각이 아니라 main에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

import java.util.Arrays;

public final class TwoPointersDemo {
    static int[] pairWithSum(int[] sorted, long target) {
        if (sorted == null) throw new IllegalArgumentException("sorted must not be null");
        int left = 0;
        int right = sorted.length - 1;
        while (left < right) {
            long sum = (long) sorted[left] + sorted[right];
            if (sum == target) return new int[] {left, right};
            if (sum < target) left++;
            else right--;
        }
        return new int[0];
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        check(Arrays.equals(pairWithSum(new int[] {1, 2, 4, 7, 11}, 9), new int[] {1, 3}), "normal");
        check(Arrays.equals(pairWithSum(new int[] {3, 3}, 6), new int[] {0, 1}), "duplicate");
        check(pairWithSum(new int[0], 1).length == 0, "empty");
        check(Arrays.equals(pairWithSum(new int[] {Integer.MAX_VALUE - 1, Integer.MAX_VALUE}, 4_294_967_293L), new int[] {0, 1}), "long sum");
        System.out.println("pair=[1, 3], duplicate=[0, 1], overflow-safe=[0, 1]");
    }
}

javac --release 21 TwoPointersDemo.java
java TwoPointersDemo

직접 실행한 출력은 다음과 같다.

pair=[1, 3], duplicate=[0, 1], overflow-safe=[0, 1]

컴파일러와 런타임은 javac 21.0.11, OpenJDK 21.0.11을 사용했다. assert 옵션에 의존하지 않고 실패 시 AssertionError를 던지므로 위 명령 그대로 검증된다.

4. overflow는 이동 방향까지 뒤집는다

int sum = sorted[left] + sorted[right]는 두 큰 양수의 합이 음수로 wraparound할 수 있다. 그러면 실제 합은 target보다 큰데 sum < target 분기로 가서 잘못된 pointer를 움직인다. Java 정수 연산은 overflow를 보고하지 않으므로 덧셈 전에 한 피연산자를 long으로 승격한다.

예제는 target도 long으로 받아 Integer.MAX_VALUE-1과 Integer.MAX_VALUE의 합을 표현한다. Math.addExact로 overflow를 예외화하는 방법도 있지만, 이 문제에서는 long domain으로 계산하는 편이 계약이 명확하다.

5. 시간·공간 복잡도

left는 최대 $n-1$번 증가하고 right는 최대 $n-1$번 감소하며 되돌아가지 않는다. 반복 횟수는 두 이동의 합보다 작으므로 $O(n)$이다. local index와 sum만 사용해 보조 공간은 $O(1)$이다.

입력이 정렬되지 않아 복사 후 정렬하면 총시간은 $O(n\log n)$, 복사 공간은 $O(n)$이고 원래 index를 보존하려면 (value,index) 객체/배열이 추가된다. HashMap two-sum은 기대 $O(n)$과 $O(n)$ 공간으로 원본 순서에서 index를 보존한다. 전처리까지 비교해야 한다.

6. JVM 실행과 메모리

int[]는 heap array object, local left/right/sum은 frame local variable 관점이다. 성공 시 new int[]{left,right}, 실패 시 new int[0] 결과 배열을 한 번 할당한다. loop 본문에는 boxing이나 collection node가 없다. 높은 호출량에서 빈 배열 allocation까지 문제라면 shared constant나 packed long 결과를 고려할 수 있지만 API 가독성과 측정 결과를 먼저 본다.

7. 패턴 변형과 대안

같은 이름 아래 이동 증명은 서로 다르다. “투 포인터니까 $O(n)$”이 아니라 각 pointer가 몇 번 움직이고 왜 되돌아가지 않는지를 설명한다.

8. 실제 도메인 적용

정렬된 timestamp stream merge, range reconciliation, ordered log diff에 쓸 수 있다. 관측 지표는 input sizes, duplicate ratio, sort/reindex time, late event rate다. 두 데이터가 이미 각각 정렬됐다면 merge pointer가 좋지만 distributed stream의 out-of-order event는 watermark/buffer 계약 없이 이 전제를 깨뜨린다.

9. 이건 피한다

• 정렬되지 않은 입력에서 합 방향으로 pointer를 움직인다. 단조성이 없어 정답을 건너뛴다. 먼저 정렬 비용을 지불하거나 hash를 쓴다.
• 같은 index를 두 번 허용한다. left <= right로 두면 값 하나를 두 번 쓸 수 있다. pair 계약이면 left < right를 유지한다.
• int로 합을 계산한다. overflow가 비교 방향을 뒤집는다. 덧셈 전에 long으로 승격한다.
• 원본 index가 필요한데 값만 정렬한다. 반환 index가 원본과 달라진다. value-index pair를 정렬하거나 HashMap을 쓴다.
• 모든 두 변수 loop를 투 포인터라 부른다. 제거 규칙과 단조성이 없으면 패턴이 아니다. 불변식을 먼저 쓴다.

Reference

• Oracle, The Java Language Specification, Java SE 21 — Integer Operations
• Oracle, Arrays.sort — Java SE 21 API
• Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition — Elementary Sorts
• Oracle, The Java Virtual Machine Specification, Java SE 21 — Heap and Frames