3. 알고리즘 투 포인터

알고리즘에서 "투 포인터"는 주어진 배열 또는 리스트에서 두 개의 포인터를 사용하여 특정 조건을 만족시키는 요소를 탐색하거나 연산을 수행하는 방법을 말합니다. 투 포인터 알고리즘은 일반적으로 선형 시간(O(n))에 해결할 수 있는 문제에 사용됩니다. 투 포인터 알고리즘은 다양한 문제에 적용될 수 있지만, 대표적인 두 가지 유형으로 나눌 수 있습니다.

예시

1. 두 수의 합 (Two Sum)

정렬된 배열에서 두 수의 합이 특정한 값을 만족하는 요소의 인덱스를 찾는 문제입니다. 다음은 투 포인터 알고리즘을 사용한 예시 코드입니다

public int[] twoSum(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[]{left, right};  // 합이 목표값과 일치하면 해당 인덱스를 반환
        } else if (sum < target) {
            left++;  // 합이 목표값보다 작으면 왼쪽 포인터를 오른쪽으로 이동
        } else {
            right--;  // 합이 목표값보다 크면 오른쪽 포인터를 왼쪽으로 이동
        }
    }

    return new int[]{-1, -1};  // 합을 찾지 못한 경우 -1을 반환
}

이 코드는 주어진 정렬된 배열에서 두 수를 선택하여 그 합이 주어진 목표값과 일치하는 경우, 해당 인덱스를 반환합니다. 만약 그러한 인덱스를 찾을 수 없으면 {-1, -1}을 반환합니다.

2. 두 수의 차이 (Two Difference)

정렬된 배열에서 두 수의 차이가 특정한 값을 만족하는 요소의 개수를 찾는 문제입니다. 다음은 투 포인터 알고리즘을 사용한 예시 코드입니다

public int twoDifference(int[] numbers, int target) {
    int count = 0;  // 차이가 목표값과 일치하는 경우의 개수를 저장하는 변수
    int left = 0;   // 배열에서 왼쪽을 가리키는 포인터
    int right = 1;  // 배열에서 오른쪽을 가리키는 포인터

    while (right < numbers.length) {  // 배열의 끝까지 반복
        int diff = numbers[right] - numbers[left];  // 현재 왼쪽과 오른쪽 포인터가 가리키는 두 수의 차이

        if (diff == target) {
            count++;  // 차이가 목표값과 일치하는 경우 개수를 증가
            left++;   // 다음 요소를 비교하기 위해 왼쪽 포인터를 오른쪽으로 이동
            right++;  // 다음 요소를 비교하기 위해 오른쪽 포인터를 오른쪽으로 이동
        } else if (diff < target) {
            right++;  // 차이가 목표값보다 작으면 오른쪽 포인터를 오른쪽으로 이동
        } else {
            left++;   // 차이가 목표값보다 크면 왼쪽 포인터를 오른쪽으로 이동
            if (left == right) {
                right++;  // 왼쪽 포인터와 오른쪽 포인터가 같은 경우 오른쪽 포인터도 이동
            }
        }
    }

    return count;  // 차이를 만족하는 요소의 개수 반환
}

이 코드는 주어진 배열에서 두 수의 차이가 주어진 목표값과 일치하는 경우의 개수를 반환합니다. 왼쪽 포인터와 오른쪽 포인터를 사용하여 배열을 탐색하고, 차이가 목표값과 일치하면 개수를 증가시키고 포인터를 이동합니다.

이와 같이 투 포인터 알고리즘은 효율적으로 정렬된 배열 또는 리스트에서 원하는 조건을 만족하는 요소를 탐색하거나 연산을 수행할 수 있습니다. 투 포인터 알고리즘은 선형 시간에 문제를 해결할 수 있는 장점이 있으며, 정렬된 데이터에서 효과적으로 동작합니다.