boj 21921

우선 처음에는 처음 for i를 돌리고 다음 for j를 돌려 각 순서의 맞는 합을 구하려 했다

for(int i=0; i<n; i++) {
        	int sum = 0;
        	if(i+x < n+1) {
        		for(int j=i; j<i+x; j++) {
        			sum = sum+arr[j];
        		}
        	}else {
        		continue;
        	}
        	if(sum > max) {
        		
        		max = sum;
        		count =1;
        	}else {
        		if(sum== max) {
        		
        			count++;
        		}
        	}
        		
        	
        }
        if(max == 0) {
        	System.out.println("SAD");
        }else {
        	  System.out.println(max);
              System.out.println(count);
        }

이런식으로 돌리면 시간 초과가 난다
우선 위의 식은 o(n^2)

근데 각 자리수 순서를 비교하는 건데 o(n^2) 이 아닌 방식이 있단 말인가??

있었다

바로바로 투포인터 혹은 슬라이딩 윈도우

허나 여기는 크기가 고정되었기 때문에 슬라이딩 윈도우로 풀었다

슬로이딩 윈도우

우선 슬리이딩 윈도우는 그림으로 보면 쉽게 이해간다

보면 크기 5인 배열에 2칸씩 잡는 것이 있다

처음엔 [0,1] 의합
다음엔 [1,2] 의합
[2,3][3,4] 로간다

즉 sum = sum - 이전값 +다음에 올값 [i(현재위치)+x(박스 크기)-1 // 현재위치가 첫 시작]
을 하면 된다
그럼 2개만 그런거 아니냐?
당연히 아니다

하나씩 움직임으로 벽이 3개 4개 5개 다 동일하다

그리고 for문 하나로 돌기 때문에 시간은 o(n) 앞선 식 보다 더욱 빨라진 것을 볼 수 있다.

문제 풀이

• 첫 i =0일때 sum 을 구한다
• i=1 일때 부터 마지막 n-x까지의 값을 구한다

n-x 까지가 마지막 값이기때문

• 각 sum의 최댓값을 구한다 count=1
• 만약 sum이 최댓값이랑 같다면 count++;

for(int i=0; i<x; i++){
	sum+= arr[i];
}

처음 sum 구하기

for(int i=1; i<=m-x; i++){
	sum = sum-arr[i-1]+arr[i+x-1] ; // 이전값빼고 다음값 더하기 
    
    if(sum >max){ // max 비교 변환
    	max = sum;
        count = 1;
    }else{
    	if(max == sum){ 현재 sum 이 max랑 같으면 증가
        	count ++;
        }

    }

} 

이런식으로 진행시 o(n) 반복문 하나만 수행

전체코드

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

class Main{
  private static int[] arr;
    
    private static int n;
    private static int x;
    private static int max = Integer.MIN_VALUE;
    private static int count =1;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        
        arr = new int[n];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<arr.length; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int sum = 0;
        for(int i=0; i<x; i++) {
        	sum += arr[i];
        }
        
        max = sum;
        
        for(int i=1; i<n-(x-1); i++) {
        	sum = sum +arr[i+x-1] -arr[i-1];
   
        	if(max < sum) {
        	
        		max = sum;
        		count=1;
        	}else {
        		if(max == sum) {
        			count++;
        		}
        	}
        }
        
        if(max != 0) {
        	System.out.println(max);
        	System.out.println(count);
        }else {
        	System.out.println("SAD");
        }
        
        
        
       
        
    }
   
}

아 이게 슬라이딩 윈도우며 슬라이딩 윈도우는 o(n)이구나 깨달았다.