12891번 문제 링크

슬라이딩 윈도우 문제로써 해당 문제는 투포인터의 활용된 문제이다. 위 문제에서 핵심 알고리즘은 이동 시, 기존의 부분문자열에서 이동 시 맨 앞을 지우고, 맨 뒤를 추가하여 최소한의 변화로 값을 비교하는 것이다.

이를 위해서 Add 메서드와 Remove 메서드를 정의해준다.

Add 메서드

    static void Add(char c){
        switch(c){
            case 'A' :
                myArr[0]++;
                if(checkArr[0] == myArr[0])
                    checkSecret++;
                break;
            ...
        }
    }

Remove 메서드

    static void Remove(char c){
        switch(c){
            case 'A' :
                if(myArr[0] == checkArr[0])
                    checkSecret--;
                myArr[0]--;
                break;
            ...
        }
    }

핵심코드

		for(int i=0; i <P; i++){ // 처음 P문자열 등록
            Add(DNA[i]);
        }
        if(checkSecret == 4) res++;
        for(int i=P; i < S; i++){
            int j = i-P;
            Add(DNA[i]);
            Remove(DNA[j]);
            if(checkSecret == 4) res++;
        }

• 위 코드는 핵심 알고리즘으로 구간을 이동하는 코드이다. 위에서 설명한대로, 맨 앞의 값은 삭제하고 뒤의 값을 추가해주면서, 확인하는 알고리즘이다.
• for(int i=P; i < S; i++){ int j = i-P; ... }

😀 성공

public 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 S = Integer.parseInt(st.nextToken()); // DNA 글자수
        int P = Integer.parseInt(st.nextToken()); // 부분 비번 글자수
        int res = 0; // 결과
        char[] DNA = new char[S];
        checkArr = new int[4]; // 체크용 배열 ACGT 만족 갯수
        myArr = new int[4]; // 부분 비번 글자 내 ACGT 갯수 
        checkSecret = 0; // ACGT 충족 시 추가
        DNA = br.readLine().toCharArray(); // DNA 배열
        
        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++){ // 처음 P문자열 등록
            Add(DNA[i]);
        }

        if(checkSecret == 4) res++;

        for(int i=P; i < S; i++){
            int j = i-P;
            Add(DNA[i]);
            Remove(DNA[j]);
            if(checkSecret == 4) res++;
        }

        br.close();
        System.out.println(res);
    }

    /**
     * 부분 문자열에 포함되는 문자를 확인, 해당 문자의 갯수 추가.
     * 추가된 갯수가 충족 갯수와 맞는지 비교 -> 맞으면 checkSecret +1
     * 
     * 기존의 문자열에서 끝에 추가되는 문자만 확인.
     * 
     * @param c
     */
    static void Add(char c){
        switch(c){
            case 'A' :
                myArr[0]++;
                if(checkArr[0] == myArr[0])
                    checkSecret++;
                break;
            case 'C' :
                myArr[1]++;
                if(checkArr[1] == myArr[1])
                    checkSecret++;
                break;
            case 'G' :
                myArr[2]++;
                if(checkArr[2] == myArr[2])
                    checkSecret++;
                break;
            case 'T' :
                myArr[3]++;
                if(checkArr[3] == myArr[3])
                    checkSecret++;
                break;
        }
    }

    /**
     * 슬라이딩 윈도우가 이동 시 제일 앞의 문자는 삭제하는데, 이를 수행하는 메서드
     * 충족 갯수와 현재 갯수가 같은경우, 추가됐었기 때문에 이를 감소시켜준다.
     * 현재 갯수를 하나 줄인다.
     * 
     * @param c
     */
    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;
        }
    }
}