99클럽 코테 스터디 5일차 TIL - 백준 2559번 : 수열

항해99 클럽 코테 스터디 5일차 TIL - 자바 미들러 4/4 (금요일)

https://www.acmicpc.net/problem/2559

✅ 문제

📌  접근방법

시간복잡도 고려

방법 1.  O(N^2)

2중 포문으로 풀면 시간초과. (2<=N<=100,000), K는 1과 N사이의 정수

근데 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.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] num = new int[N];
        st = new StringTokenizer(br.readLine());

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

        int Max = 0;

        for (int i = 0; i < K; i++) {
            Max += num[i];
        }

        int Sum = Max;
        for (int i = K; i < N; i++) {
            Sum -= num[i - K];
            Sum += num[i];
            if (Max < Sum) Max = Sum;
        }

        System.out.println(Max);

    }
}
// 2중 for문으로 풀면 시간초과 (최악의 케이스 5만(10만의 절반) * 5만 = 25억)
// 2중 for문 안 돌리고 슬라이딩 윈도우로 풀면 O(N)

 

실행코드

http://boj.kr/053ec6208cd841f4b7648bba628c675d

TIL

슬라이딩 윈도우 개념 강의