[24/10/10] 코테 슬라이딩 윈도우

백준 12891번

 

2개의 포인터로 범위의 양끝을 가르키고 그 양끝을 기준으로 문제를 해결한다.

 

1) 처음에는 윈도우를 잡고 그 다음부터는 for문으로 옆으로 땡기면서 관찰하면 된다.

그렇게 땡기게되면 모든 배열을 윈도우로 순회할때 O(n) , 윈도우의 맨 앞 원소는 삭제되고 뒤에서부터 하나는 추가되기에 삭제되고 추가되는 총 2개의 원소들만 작업 처리해주면 된다. 

 

2) 삭제,추가되는 원소들에 대해 구하고자 하는 기준과 비교해야되는데 현재 윈도우 안에서의 원소들에 대하여 카운트 하고 있는 배열이 있을거고 맞으면 답이 되는 기준배열이 있을것이다. 매 윈도우 이동마다 기준배열과 카운트 배열을 무식하게 하나씩 비교하면 이 또한 O(N)만큼 소요될 것이다. 하지만 슬라이딩을 원소의 추가/삭제 기준으로 본다면 추가되는 원소로 인한 카운트 배열 업데이트 , 삭제되는 원소로 인한 카운트 배열 업데이트 해주고 다시 처음부터 배열끼리 비교하는것보다 추가/제거된 것으로 인한 부분만 다시 비교해주면 된다.

import java.util.*;
import java.lang.*;
import java.io.*;

/*
총 S개 >> index S-1 
0 1 2 3 4 5 6 7 8 (9, 4) : 6개 
P개
0 1 2 3 
1 2 3 4 
2 3 4 5

for (n=0; n<S-P+1; n++) 시작 인덱스 i , 끝 인덱스 i+P-1 , 끝 인덱스 S-1 , 횟수 :  P-1 ~ S-1  : S-P+1
시작 index = 0;
끝 index = 시작 index+P-1;
for(i=start_index; i<start_index+P-1; i++) >> O(P*(S)) >> O(P*S) == 1 0000 0000 0000 >> 불가능
*/


/*
전체 배열을 부분문자열만큼 정해서 순회하는건 불가피함. 여기서 for문 한개
들어오는 문자열, 나가는 문자열만 확인해야 여기서 for문을 또 안씀
*/

class Main {
    //체크 갯수 기준 배열
    static int[] checkArr = new int[4];
    //현재 배열에서의 체크 현황 배열
    static int[] myArray = new int[4];
    static int checkSecret=0;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        char[] arrayS=new char[S];
        int P = Integer.parseInt(st.nextToken());
        int result=0;

        arrayS=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<P; i++){
            add(arrayS[i]);
        }     

        if(checkSecret==4){
            result++;
        }

        for(int i=P; i<S; i++){
            add(arrayS[i]);
            remove(arrayS[i-P]); 

            if(checkSecret==4){
                result++;
            }
        }
        System.out.println(result);
        
        
    }
    static void add(char c){ //A C G T 
        switch (c) {
            case 'A':
                myArray[0]++;
                if(myArray[0]==checkArr[0])
                    checkSecret++;
                break;
            case 'C':
                myArray[1]++;
                if(myArray[1]==checkArr[1])
                    checkSecret++;
                break;
            case 'G':
                myArray[2]++;
                if(myArray[2]==checkArr[2])
                    checkSecret++;
                break;
            case 'T':
                myArray[3]++;
                if(myArray[3]==checkArr[3])
                    checkSecret++;
                break;
        }
    }

    static void remove(char c){
        switch (c) {
            case 'A':
                if(myArray[0]==checkArr[0])
                    checkSecret--;
                myArray[0]--;
                break;
            case 'C':
                if(myArray[1]==checkArr[1])
                    checkSecret--;
                myArray[1]--;
                break;
            case 'G':
                if(myArray[2]==checkArr[2])
                    checkSecret--;
                myArray[2]--;
                break;
            case 'T':
                if(myArray[3]==checkArr[3])
                    checkSecret--;
                myArray[3]--;
                break;
        }
    }
}