7-2. 슬라이딩 윈도우

개념

정의

• 정의: 투 포인터로 범위를 지정한 다음 범위(window)를 유지한채로 이동(sliding)하며 문제를 해결하는 방법

 

중요

• 전체 크기(N)와 윈도우 크기(M)이 있을때, 핵심은 시간 복잡도를 O(NM)이 아닌 O(N)으로 진행하는 것
  • 즉, 교집합의 정보를 공유하고, 차이가 발생하는 양쪽 끝 원소만을 갱신하는 방법

 

언제 사용?

특정 범위를 지속해서 탐색하는 경우

int count = 0;
//투 포인터 선언
int s_index = 0;
int e_index = P-1;

while(e_index < S-1){
    if(hm.get('A') >= A && hm.get('C') >= C && hm.get('G') >= G && hm.get('T') >= T){
        count++;
    }

	//차이가 발생하는 왼쪽 부분 처리
    /// 기존에 있던 왼쪽 부분 삭제
    hm.put(ctr[s_index], hm.get(ctr[s_index]) - 1);
    s_index++;

	//차이가 발생하는 오른쪽 부분 처리
    /// 새로 들어오는 오른쪽 부분 삽입
    e_index++;
    hm.put(ctr[e_index], hm.get(ctr[e_index]) + 1);
}