[24/11/3] 슬라이딩 윈도우

12891

저번에 참고해서 푼거 복습할겸 다시 풀어봤다.

3칸을 매 반복 안에서 모든 요소를 다시 확인하면 결국 O(SP) 복잡도가 되어서 시간초과가 날 것이다. 윈도우를 이동하면 항상 추가된 요소만 반영, 나가는 요소도 반영 즉 O(2)의 상수복잡도만 고려해도 되어서 O(N)에서 끝길 수 있다.

import java.util.*;
import java.lang.*;
import java.io.*;
//A C G T
// The main method must be in a class named "Main".
class Main {
    static int start=0;
    static int end=0;
    static int count=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());
        int P = Integer.parseInt(st.nextToken());
        char[] arr = br.readLine().toCharArray();
        int[] stdArr = new int[4];
        int[] countArr= new int[4];
        for(int i=0; i<4; i++){
            countArr[i]=0;
        }
        st = new StringTokenizer(br.readLine());

        for(int i=0; i<4; i++){
            stdArr[i]=Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<P; i++){
            addElement(arr,countArr);
        }

        if(isSameArr(stdArr,countArr)){
            count++;
        }
        //초기 카운트 배열과 start, end 반영

        while(end<S){
            //제거되는거 제거시키고 카운트배열에 반영
            removeElement(arr,countArr);
            //추가되는거 추가시키고 카운트배열에 반영
            addElement(arr,countArr);
            //기준배열과 카운트배열 같으면 O(4)
            if(isSameArr(stdArr,countArr)){
                count++;
            }
            //카운트 추가
        }
        System.out.printf("%d",count);



    }
    public static void addElement(char[] arr, int[] countArr){
        //index에 해당하는거 stdArr에 반영
        switch (arr[end]) {
            case 'A':
                countArr[0]++;
                break;
            case 'C':
                countArr[1]++;
                break;
            case 'G':
                countArr[2]++;
                break;
            case 'T':
                countArr[3]++;
                break;
        }
        end++;
    }
    public static void removeElement(char[] arr, int[] countArr){
        //index에 해당하는거 stdArr에 반영
        switch (arr[start]) {
            case 'A':
                countArr[0]--;
                break;
            case 'C':
                countArr[1]--;
                break;
            case 'G':
                countArr[2]--;
                break;
            case 'T':
                countArr[3]--;
                break;
        }
        start++;
    }

    public static boolean isSameArr(int[] arr1, int[] arr2){
        for(int i=0; i<4; i++){
            if(arr1[i]>arr2[i]){
                return false;
            }
        }
        return true;
    }

}

 

 

 

 

12847

마찬가지로 초기 배열 길이 잡아놓고 윈도우 슬라이딩 시키면서 빠지는거 업데이트, 들어오는거 업데이트 시키면 된다.

 

주의할건 270만까지 저장 가능한 int 로 습관적으로 했다가   (0 < Ti ≤ 1,000,000) 에 걸려서 오버플로우 나버리면 테케 통과 못한다. 숫자 백만 단위로 커지면 long을 쓰자.

import java.util.*;
import java.lang.*;
import java.io.*;
//A C G T
// The main method must be in a class named "Main".
class Main {
    static int end=0;
    static int start =0;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long max =0;
        
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        long total =0;
        for(int i=0; i<m; i++){
            total = addElement(arr,total);
            max=total;
        }
        while(end<n){
            long temp = addElement(arr,total);
            temp = removeElement(arr,temp);
            if(temp>max){
                max=temp;
            }
            total=temp;
        }
        System.out.printf("%d",max);

    }
    public static long addElement(int[] arr,long total){
        long temp =0 ;
        temp= total + arr[end];
        end++;
        return temp;
    }

    public static long removeElement(int[] arr , long total){
        long temp=0;
        temp=total-arr[start];
        start++;
        return temp;
    }
}