투 포인터 알고리즘이란 배열에서 2개의 포인터로 범위를 지정해 원하는 값을 얻는 방식입니다.
배열의 범위를 지정할 시작점(start)/끝점(end) 포인터를 두고 이동시키면서 원하는 값을 얻습니다.
끝점과 시작점을 배열의 처음부터 한 칸씩 이동시키는 방식으로 범위를 변경하면서 목표 값을 얻을 수 있습니다.
포인터를 이동시키는 기준은 아래와 같이 정리할 수 있습니다.
1. 범위(start~end)의 합이 목표 값보다 큰 경우 시작점 이동 (start++)
2. 끝점이 배열의 끝에 도달한 경우 시작점 이동 (start++)
3. 범위의 합이 목표 값보다 작은 경우 끝점 이동 (end++)
4. 범위의 합이 목표 값과 같은 경우 일치하는 개수 증가, 시작점 이동 (cnt++, start++)
범위의 합이 6인 경우의 수를 찾는 예제를 보면서 이해를 해보면 좋을 것 같습니다.
처음 범위의 합(sum)은 2이므로 목표 값인 6보다 작기에 end를 증가시킵니다.
end를 증가시킨 후 sum=6으로 목표 값과 일치하기에 start, cnt를 증가시킵니다.
sum의 값이 다시 목표 값보다 작기에 end를 증가시킵니다.
end를 증가시킨 후 sum=6으로 목표 값과 일치하기에 start, cnt를 증가시킵니다.
sum이 목표 값보다 작기에 end를 증가시키지만 그래도 목표 값보다 작기에 end를 한번 더 증가시킵니다.
sum의 값이 목표 값보다 크기에 start를 증가시킵니다.
start를 증가시킨 후 sum=6으로 목표 값과 일치하기에 start, cnt를 증가시킵니다.
sum의 값이 다시 목표 값보다 작기에 end를 증가시킵니다.
end가 배열의 끝에 도달하였기에 start를 증가시킵니다.
start또한 배열의 끝에 도달하였기에 탐색을 종료합니다.
위의 과정을 코드로 구현하면 아래와 같습니다.
|
package com.algorithm;
public class TwoPointer {
public static void main(String[] args){
int[] arr= {2,4,2,1,5};
int cnt=0; // 목표 값의 갯수
int start=0, end=0, sum=0; // 시작점, 끝점, 합계
int result=6; // 목표 값
while(start!=arr.length) {
if(sum==result) { //1. 합계와 목표값이 같은 경우 시작점, 갯수 증가
sum-=arr[start];
start++;
cnt++;
} else if(sum>result||end>=arr.length) { //2. 합계가 목표값보다
sum-=arr[start]; // 크거나 끝점이 배열 길이를 넘은 경우
start++;
} else { //3. 합계가 목표값보다 적은 경우
sum+=arr[end++];
}
}
System.out.println(cnt);
}
}
|
[참고사이트]
'알고리즘' 카테고리의 다른 글
| 브루트 포스(Brute Force) 알고리즘 (0) | 2021.05.20 |
|---|
