[99클럽 코테스터디 5일차 TIL] 수열 (슬라이딩 윈도우)

 

📌 오늘의 키워드 

• 누적 합
• 투 포인터
• 슬라이딩 윈도우 
  
  

📌 문제 파악 

 

 

방법 1.  O(N**2)

일단 그냥 시간 복잡도 고려하지 않고 생각나는건 2중 포문입니다. 

근데 K가 N에 가까워 지는 순간 시간 복잡도는 최악의 경우 O(NK) -> O(N**2)이 된다. 

그러면 당연히~ 1초 넘는다. 

 

방법 2.  O(N)

그러면 어떻게 풀 수 있을까 내가 생각한 방식은 슬라이딩 윈도우다. 인덱스 0번 지점부터 k-1번까지 미리 누적합을 구해둔 후, 윈도우를 한칸씩 밀어나가는거다. 그러면 탐색 과정에서 바로 직전의 인덱스를 제외하고, i + k 번째 값을 추가하면 된다. 

그러면 2중 포문이 아니라 단일 포문으로 가능해지는 것이다. 

 

 

📌 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.PreparedStatement;
import java.util.*;

class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력1 : N _ 온도를 측정한 전체 날짜 수, K : 연속적인 날짜의 수
        String readLine = br.readLine();
        String[] NK = readLine.split(" ");
        int n = Integer.parseInt(NK[0]);
        int k = Integer.parseInt(NK[1]);

        // 입력2 : N일 동안 측정한 온도 int 배열
        readLine = br.readLine();
        String[] tempLine = readLine.split(" ");
        int [] temperatures = new int[n+1];

        for(int i=0; i<n; i++) {
            temperatures[i] = Integer.parseInt(tempLine[i]);
        }

        // 로직 :
        // 1. 2중 포문 : 최대 O(N^2) -> 10^10 -> 1초 초과 (불가능)
        // 2. 슬라이딩 윈도우 : 이전 계산 값을 저장하면서 진행. 0(N) -> 10 ^ 5 -> 1초 이내
        int memo = 0;
        int max = 0;

        for (int i=0; i<k; i++){
            memo += temperatures[i];
        }

        max = memo;
        for (int i=1; i<n-k+1; i++){
            memo = memo - temperatures[i-1] + temperatures[i+k-1];
            max = Math.max(max,memo);
        }

        // 출력 : 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력
        System.out.println(max);
    }
}