---
title: "투 포인터: 단조성을 근거로 후보 쌍을 한 번에 버리는 Java 패턴"
slug: "java-two-pointers"
category: "CS"
topic: "cs"
subtopic: "problem-solving-patterns"
tags: ["Java","Two Pointers","Sorted Array","Invariant","Overflow"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "정렬 배열의 합 문제에서 left/right 이동이 왜 정답 후보를 버리지 않는지 증명하고, long 승격·중복·정렬 비용·부적합 반례까지 분석한다."
kind: "Deep Dive"
evidence: "JLS 21 정수 연산·Oracle Arrays API·Princeton 정렬 자료를 대조하고 TwoPointersDemo의 중복·빈 배열·int 합 overflow 경계를 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

투 포인터는 변수 두 개를 선언하는 기법이 아니다. 한쪽 경계를 움직일 때 제거되는 후보에 정답이 없다는 **단조성**이 있어야 한다. 대표 예제는 오름차순 배열에서 합이 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를 추적한다.

| left/right | 합 | 판단 | 한 번에 제거되는 후보 |
| --- | ---: | --- | --- |
| 0/4 | 12 | 큼 → right-- | `(1,11)`부터 `(7,11)`까지 11을 오른쪽으로 둔 후보 |
| 0/3 | 8 | 작음 → left++ | `(1,2)`부터 `(1,7)`까지 1을 왼쪽으로 둔 후보 |
| 1/3 | 9 | 일치 | index `[1,3]` |

합이 너무 크면 현재 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/right | 합 | 제거되는 후보 |
| --- | ---: | --- |
| 0/4 | 5 | `-4`를 포함한 모든 쌍 |
| 1/4 | 8 | `-1`을 포함한 모든 쌍 |
| 2/4 | 11 | `2`를 포함한 모든 쌍 |
| 3/4 | 14 | `5`를 포함한 모든 쌍 |

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

## 실행 재현

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

```java
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]");
    }
}
```

```bash
javac --release 21 TwoPointersDemo.java
java TwoPointersDemo
```

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

```text
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. 패턴 변형과 대안

| 문제 | pointer 의미 | 이동 근거 |
| --- | --- | --- |
| 정렬 two-sum | 양 끝 후보 | 합의 단조성 |
| palindrome | 양 끝 문자 | 대칭 위치 일치 |
| merge | 두 정렬 입력의 현재 최소 | 각 입력의 suffix 정렬 |
| fast/slow | traversal 속도 | linked cycle/중간점 관계 |

같은 이름 아래 이동 증명은 서로 다르다. “투 포인터니까 $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](https://docs.oracle.com/javase/specs/jls/se21/html/jls-4.html#jls-4.2.2)
- Oracle, [Arrays.sort — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Arrays.html#sort(int%5B%5D))
- Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition — Elementary Sorts](https://algs4.cs.princeton.edu/21elementary/)
- Oracle, [The Java Virtual Machine Specification, Java SE 21 — Heap and Frames](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5)