- 배열이나 리스트에서 '두 개의 포인터'를 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘입니다. 일반적으로 배열이나 리스트가 '정렬되어 있을 때' 사용됩니다.
- 투 포인터 알고리즘은 보통은 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킵니다. - 또는 동일한 시점을 기점으로 왼쪽 포인터를 고정한 상태에서 오른쪽 포인터를 이동하고, 조건에 따라 왼쪽 포인터도 이동하며 탐색하는 방식을 가집니다. - 해당 알고리즘은 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 데 사용될 수 있습니다.
- 주어진 정수 배열에서 두 개의 숫자를 선택하여 합이 특정한 값을 갖는지 확인하는 문제입니다. - 투 포인터 알고리즘을 사용하면 선형 시간에 문제를 해결할 수 있습니다.
💡 간단한 예시
- 주어진 정수 배열에서 두 개의 숫자를 선택하여 합이 특정한 값(target)을 갖는지 확인하는 문제를 해결합니다.
1. left와 right라는 두 개의 포인터를 배열의 양 끝에서 시작합니다.
2. left 값보다 right 값이 큰 경우일 때까지 반복합니다.
3. left와 right의 합을 sum에 저장합니다.
4.1. 만약 sum이 target과 같다면, count 값을 증가하며 left 인덱스는 오른쪽으로 이동하며 right 인덱스는 왼쪽으로 이동합니다.
4.2. 그렇지 않고 sum이 target보다 작다면, left를 한 칸 오른쪽으로 이동시킵니다.
4.3. sum이 target보다 크다면, right를 한 칸 왼쪽으로 이동시킵니다.
6. 해당 조건에 만족하는 count 값을 반환합니다.
/**
* 01. 투 포인터 합 문제 (Two Sum Problem)
* 주어진 정수 배열에서 두 개의 숫자를 선택하여 합이 특정한 값(target)을 갖는지 확인하는 문제를 해결합니다.
*
* @return ResponseEntity<ApiResponse>
* @link
* @since 2024.01.
*/@GetMapping("/1")public ResponseEntity<Object> question01() {
int[] nums = {1, 2, 3, 4, 5, 6, 7};
inttarget=12;
intcount=0;
// 1. left와 right라는 두 개의 포인터를 배열의 양 끝에서 시작합니다.intleft=0;
intright= nums.length - 1;
// 2. left 값보다 right 값이 큰 경우일때까지 반복합니다.while (left < right) {
// 3. left와 right의 합을 sum에 저장합니다.intsum= nums[left] + nums[right];
// 4.1. sum이 target과 같다면, count 값을 증가하며 left 인덱스는 오른쪽으로 이동하며 right 인덱스는 왼쪽으로 이동합니다.if (sum == target) {
count++;
left++;
right--;
}
// 4.2. sum이 target보다 작다면, left를 한 칸 오른쪽으로 이동시킵니다.elseif (sum < target) {
left++;
}
// 4.3. sum이 target보다 크다면, right를 한 칸 왼쪽으로 이동시킵니다.else {
right--;
}
}
// 5. 해당 조건에 만족하는 count 값을 반환합니다.returnnewResponseEntity<>(count, HttpStatus.OK);
}
💡 이미지로 이해하기
- 해당 조건에 만족할 때까지 left는 오른쪽으로 이동하고 합을 찾습니다. 최종 값을 찾으면 count ++를 해줍니다.
