[Algorithm]투 포인터(Two Pointer)
투 포인터
배열의 특정 구간을 연속적으로 처리하는 알고리즘이다.
배열에서 연속된 데이터 구간에서 처리하기를 원하거나, 정렬된 두 배열이 문제 조건에 있다면, 투포인터 알고리즘을 의심해봐야 한다.
🧐 알고리즘
- 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
- 현재 부분 합이 M과 같다면, 카운트한다.
- 현재 부분 합이 M보다 작거나 같다면, end를 1 증가시킨다.
- 현재 부분 합이 M 보다 크다면, start를 1 증가시킨다.
- 모든 경우를 확인할 때까지 2~4 과정 반복
👨💻 소스
import java.util.*;
public class TwoPointer {
public static void main(String[] args){
int[] arr = {1, 2, 3, 2, 5};
int count = 0;
int end = 0;
int sum = 0;
for(int start = 0 ; start < arr.length ; start++) {
while(sum < 5 && end < arr.length) {
sum += arr[end];
end += 1;
}
if(sum == 5) {
count++;
}
sum -= arr[start];
}
System.out.println(count);
}
}
🏅 관련 문제
Author And Source
이 문제에 관하여([Algorithm]투 포인터(Two Pointer)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@thehill_hannam/투-포인터Two-Pointers저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)