투 포인터 알고리즘이란?
- 리스트를 탐색할때 효과적으로 탐색하기 위해 두개의 포인터로 위치를 기록하면서 탐색하는 알고리즘
- 이중반복문으로 처리해야할 문제를 반복문 하나로 처리 가능하게하여 시간복잡도를 줄여준다.
예제문제 - 최대 길이 연속부분수열
0과 1로만 구성된 길이가 N인 수열이 주어졌다. 이 수열에서 k번을 0을 1로 변경할 수 있고 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 만들어보자.
-ex
만약 길이가 14인 수열이 주어지고 k = 2라면
11001101101101
우리가 만들 수 있는 최대 길이의 연속부분수열은 110011111111 로 길이는 8 이다.
이를 투 포인터 알고리즘으로 구현해보자.
접근 방법
1. for문으로 rt라는 포인터를 0부터 수열의 길이만큼 증가시키며 수열을 탐색한다. 탐색 중 0을 만나면 cnt라는 변수를 0 부터 하나씩 증가시키며 0을 1로바꾼 횟수를 저장시킨다.(cnt는 최대 k값만큼 커질 수 있다)
2. lt = 0으로 초기화 해놓고 rt가 0을 만났을 때 cnt횟수를 확인하며 k보다 커진다면 lt값을 0을 만날때까지 증가시키고 0을 만날시에 cnt를 다시 1 감소시킨다.
3.여기서 rt-lt+1이 각 탐색한 수열의 길이이다. 이 값의 최대가 최대 길이의 연속부분수열이다.
코드(Java)
public class Main {
//매개변수로 수열arr, 수열의크기n, 바꾸기 가능한 횟수k를 받는다.
static int solution(int[] arr,int n, int k) {
int answer = 0, lt = 0, cnt = 0;
//rt값을 증가시키며 탐색 시작
for (int rt = 0; rt < n; rt++) {
if (arr[rt] == 0) cnt++; //0을 만나면 0을1로 바꾸었다고 가정하고 cnt값 증가
while (cnt > k) {//rt값을 증가시키고 cnt가 만약 k보다 커졌다면 lt값을 증가시키며 0을 만나면 1로바꾼0을 원상복구
if(arr[lt] == 0) cnt--;
lt++;
}
answer = Math.max(answer,rt-lt+1);
}
return answer;
}
}
backend developer