[do it 알고리즘] 백준 12891 (슬라이딩 윈도우)

문제 설명

 

풀기 전 생각

• 배열에 입력받은 String 저장
• 시작 index를 설정하여 배열길이까지 반복
• 시작 index가 'A', 'C', 'G', 'T'에 해당하면 그 값++
• 부분문자열 길이만큼 돌았으면 중간 점검으로 만족하는지 확인
• 시작 index를 다시 앞으로 당기고 다른 변수는 다 0으로 초기화해서 하나씩 확인

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

public class Main {
    public static void main(String[] args)throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int stringLen = Integer.parseInt(st.nextToken());
        int subStringLen = Integer.parseInt(st.nextToken());

        String str = bf.readLine();
        char[] arr = str.toCharArray();
        st = new StringTokenizer(bf.readLine());
        int needA = Integer.parseInt(st.nextToken());
        int needC =  Integer.parseInt(st.nextToken());
        int needG =  Integer.parseInt(st.nextToken());
        int needT =  Integer.parseInt(st.nextToken());
        int start_index = 0;
        int cnt = 0;
        int countA = 0;
        int countC = 0;
        int countG = 0;
        int countT = 0;
        int sumcnt = 0;
        while(start_index < stringLen){
            sumcnt++;
            if(arr[start_index] == 'A'){
                countA++;
            }else if(arr[start_index] == 'C'){
                countC++;
            }
            else if(arr[start_index] == 'G'){
                countG++;
            }
            else if(arr[start_index] == 'T'){
                countT++;
            }
            start_index++;
            if(sumcnt >= subStringLen){
                if(countA >= needA && countC >= needC && countG >= needG && countT >= needT){
                    cnt++;
                }
                start_index = start_index - subStringLen+1;
                sumcnt = 0;
                countA = 0;
                countC = 0;
                countG = 0;
                countT = 0;
            }
        }
        System.out.println(cnt);

    }
}

오류 및 개선

• 테스트 입력은 통과했지만 시간초과
• 슬라이딩 윈도우 개념을 보니 초기 1회 실행
• 그 후, 앞을 빼고 뒤를 더해나가며 시간복잡도를 줄이기
• 함수를 정의하여 가시성 높이기

최종

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

public class Baek12891 {
    static int[] leastNeed = new int[4]; // 'A' 'C' 'G' 'T'
    static int[] myAlpha = new int[4]; // 'A' 'C' 'G' 'T'
    static int satisfied = 0; // 'A' 'C' 'G' 'T'가 만족한 갯수
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int StringLen = Integer.parseInt(st.nextToken());
        int subStringLen = Integer.parseInt(st.nextToken());
        int cnt = 0;

        char [] myString = bf.readLine().toCharArray(); // 문자열 배열로 저장
        st = new StringTokenizer(bf.readLine());

        for(int i = 0; i < 4; i++){
            leastNeed[i] = Integer.parseInt(st.nextToken()); // [0] : A [1] : C [2] : G [3] : T 최소 개수 저장
            if(leastNeed[i] == 0) {satisfied++;}
        }

        for(int i=0; i < subStringLen; i++){ // 초기값 넣기
            Add(myString[i]);
        }
        if(satisfied == 4) {cnt++;} // 초기값이 만족하는지 확인


        for(int i = subStringLen, j=0; i < StringLen; i++,j++){ // 슬라이딩 윈도우
            Add(myString[i]);
            Remove(myString[j]);
            if(satisfied == 4){cnt++;}
        }
        System.out.println(cnt);
        bf.close();

    }
    public static void Add(char c){
        switch (c){
            case 'A' : myAlpha[0]++;
                if(myAlpha[0] == leastNeed[0]){satisfied++;}
                break;
            case 'C' : myAlpha[1]++;
                if(myAlpha[1] == leastNeed[1]){satisfied++;}
                break;
            case 'G' :  myAlpha[2]++;
                if(myAlpha[2] == leastNeed[2]){satisfied++;}
                break;
            case 'T' : myAlpha[3]++;
                if(myAlpha[3] == leastNeed[3]){satisfied++;}
                break;
        }
    }
    public static void Remove(char c){
        switch (c){
            case 'A' :
                if(myAlpha[0] == leastNeed[0]){satisfied--;}
                myAlpha[0]--;
                break;
            case 'C' :
                if(myAlpha[1] == leastNeed[1]){satisfied--;}
                myAlpha[1]--;
                break;
            case 'G' :
                if(myAlpha[2] == leastNeed[2]){satisfied--;}
                myAlpha[2]--;
                break;
            case 'T' :
                if(myAlpha[3] == leastNeed[3]){satisfied--;}
                myAlpha[3]--;
                break;
        }
    }
}

참고

투 포인트 알고리즘 : 구간의 넓이가 조건에 따라 유동적 변화
슬라이딩 윈도우 알고리즘 : 구간의 넓이가 고정