투 포인터, 슬라이딩 윈도우

📝 투 포인터와 슬라이딩 윈도우 알고리즘은 배열, 문자열, 리스트와 같은 순차적인 데이터 구조에서 연속적인 부분 집합을 처리하는 알고리즘 기법이다.
두 알고리즘은 이중 for문을 사용하여 시간 복잡도가 $O(N^2)$이 걸리는 문제를 $O(N)$으로 최적화 시키는데 사용하며, 주요 차이점은 부분 배열의 크기 변화 여부이다.

---

1. 투 포인터(Two Pointers)

투 포인터는 배열이나 리스트를 순차적으로 탐색할 때 두 개의 포인터를 사용하여 특정한 조건을 만족하는 부분집합을 찾는 알고리즘이다.
탐색 시 🎯부분 배열의 크기가 가변적이며, 주로 정렬된 배열 또는 리스트의 탐색에 사용된다.
(연속된 부분 배열을 탐색할 때 사용 가능하기 때문에, 정렬을 통해 연속성을 추가해야하는 경우가 있다.)

---

2. 슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우는 고정된 크기의 윈도우(창)를 사용하여 배열 또는 문자열을 순차적으로 탐색하는 알고리즘이다.
탐색 시 🎯부분 배열의 크기가 고정적 이며, 주로 배열이나 문자열 등의 비정렬 데이터의 탐색에 사용된다.
고정적인 부분 배열의 크기가 있기 때문에, 포인터 변수가 1개만 있어도 된다.

---

3. 예제 코드(투 포인터)

📌 문제: 백준 2003. 수들의 합 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		 StringTokenizer st=new StringTokenizer(in.readLine()," ");
		 
		 int N=Integer.parseInt(st.nextToken()); // 수열의 크기
		 int M=Integer.parseInt(st.nextToken()); // 만들어야 하는 수
		 
		 // 수열 입력
		 int[] arr=new int[N];
		 st=new StringTokenizer(in.readLine()," ");
		 for(int i=0;i<N;i++) {
			 arr[i]=Integer.parseInt(st.nextToken());
		 }
		 
		 // 투 포인터 알고리즘
		 int start=0, end=0, answer=0, sum=0;
		 while(start<=end) {	
			 
			 if(sum==M) answer++;
			 
			 // 현재 부분 집합의 합이 M(만들어야하는 수)보다 큰 경우
			 if(sum > M) {
				 sum-=arr[start];
				 start++;
			 }
			 else if(end==N) {
				 break;
			 }
			 else {
				sum+=arr[end];
				end++;
			 }
		 }
		 
		 // 출력
		 System.out.println(answer);
	}
}

---

4. 예제 코드(슬라이딩 윈도우)

📌 문제: 백준 12891. DNA 비밀번호

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(in.readLine()," ");
		
		int N=Integer.parseInt(st.nextToken()); 	// DNA 문자열의 길이
		int P=Integer.parseInt(st.nextToken());		// 비밀번호로 사용할 부분 문자열의 길이
		
		String DNA=in.readLine();	// DNA 문자열
		int[] minCnt=new int[4]; 	// 부분문자열에 포함되어야 할 {A,C,G,T}의 최소 개수
		int[] codeCnt=new int[4]; 	// 문자{A,C,G,T}의 개수를 저장할 배열
		int answer=0;				// 비밀번호의 종류의 수(출력할 값)
		
		st=new StringTokenizer(in.readLine()," ");
		for(int i=0;i<4;i++) {
			minCnt[i]=Integer.parseInt(st.nextToken());
		}
		
		// 1. 슬라이딩 윈도우를 실행하기 전, 맨 앞 문자열을 생성하고 체크해준다.
		// 1-1. 맨 앞 비밀번호 생성
		for(int i=0; i<P; i++) {
			if(DNA.charAt(i)=='A') {
				codeCnt[0]++;
			}
			else if(DNA.charAt(i)=='C') {
				codeCnt[1]++;
			}
			else if(DNA.charAt(i)=='G') {
				codeCnt[2]++;
			}
			else if(DNA.charAt(i)=='T') {
				codeCnt[3]++;
			}
		}

		// 1-2. 맨 앞 비밀번호가 유효한지 체크
		boolean check=true;
		for(int i=0; i<4; i++) {
			// 한개라도 최소한의 코드수를 못맞추면
			if(codeCnt[i] < minCnt[i]) {
				check=false;
			}
		}
		if(check) answer++;
		
		
		// 2. 슬라이딩 윈도우 알고리즘
		for(int i=0; i<N-P; i++) {	// i: Start Point		
			// 2-1. Start Point의 값 빼기
			if(DNA.charAt(i)=='A') {
				codeCnt[0]--;
			}
			else if(DNA.charAt(i)=='C') {
				codeCnt[1]--;
			}
			else if(DNA.charAt(i)=='G') {
				codeCnt[2]--;
			}
			else if(DNA.charAt(i)=='T') {
				codeCnt[3]--;
			}
			
			// 2-2. End Point를 한칸 이동 후 값 더하기
			if(DNA.charAt(i+P)=='A') {
				codeCnt[0]++;
			}
			else if(DNA.charAt(i+P)=='C') {
				codeCnt[1]++;
			}
			else if(DNA.charAt(i+P)=='G') {
				codeCnt[2]++;
			}
			else if(DNA.charAt(i+P)=='T') {
				codeCnt[3]++;
			}
			
			// 2-3. 비밀번호가 유효한지 체크
			check=true;
			for(int j=0;j<4;j++) {
				// 한개라도 최소한의 코드수를 못맞추면
				if(codeCnt[j] < minCnt[j]) {
					check=false;
				}
			}
			if(check) {
				answer++;
			}
		}
		
		// 출력
		System.out.println(answer);
	}
}