[코테 알고리즘] 슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우(Sliding Window)

---

N개의 원소를 갖는 배열과 w 너비의 창문
창문을 한칸씩 오른쪽으로 이동할 때,
(매순간 창문 안에서의 정보 노출 필요)
Window를 한칸 옮기면 w-1칸은 겹친다
이전의 결과를 써먹는 방향으로 접근하자

🕑 시간복잡도: O(N)
[ 맨 처음 Window에 대해서만 O(w) ]

슬라이딩 윈도우(Sliding Window) 코드 구현

---

<백준 알고리즘, 12891번>

import java.util.*;
import java.io.*;
class Main {
  static int[] checkArr;
  static int[] myArr;
  static int checkSecret;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());
    int result = 0;
    char[] A = new char[N];
    checkArr = new int[4];
    myArr = new int[4];
    checkSecret = 0;

    A = br.readLine().toCharArray();

    st = new StringTokenizer(br.readLine());
    for(int i = 0; i < 4; i++) {
      checkArr[i] = Integer.parseInt(st.nextToken());
      if(checkArr[i] == 0) {
        checkSecret++;
      }
    }

    for(int i = 0; i < K; i++) {
      Add(A[i]);
    }
    if(checkSecret == 4) 
      result++;

    // 슬라이딩 윈도우 처리부분
    for(int i = K; i < N; i++) {
      int j = i - K;
      Add(A[i]);
      Remove(A[j]);
      if(checkSecret == 4) {
        result++;
      }
    }
    System.out.println(result);
    br.close();
  }
  public static void Add(char c) {
    switch(c) {
      case 'A':
        myArr[0]++;
        if(myArr[0] == checkArr[0])
          checkSecret++;
        break;
      case 'C':
        myArr[1]++;
        if(myArr[1] == checkArr[1])
          checkSecret++;
        break;
      case 'G':
        myArr[2]++;
        if(myArr[2] == checkArr[2])
          checkSecret++;
        break;
      case 'T':
        myArr[3]++;
        if(myArr[3] == checkArr[3])
          checkSecret++;
        break;  
    }
  }
  private static void Remove(char c) {
    switch(c) {
      case 'A':
        if(myArr[0] == checkArr[0])
          checkSecret--;
        myArr[0]--;
        break;
      case 'C':
        if(myArr[1] == checkArr[1])
          checkSecret--;
        myArr[1]--;
        break;
      case 'G':
        if(myArr[2] == checkArr[2])
          checkSecret--;
        myArr[2]--;
        break;
      case 'T':
        if(myArr[3] == checkArr[3])
          checkSecret--;
        myArr[3]--;
        break;  
    }
  }
}