[인프런 알고리즘] Chpater 3, 3번 문제(최대 매출)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

첫 번째 코드(중첩 for 문)

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

public class sec03_03 {
    public static int solution(int N, int M, int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < N - (M - 1); ++i)
        {
            int tempSum = 0;
            for(int j = i; j < N - (N - M) + i; ++j) tempSum += arr[j];

            if(tempSum > max) max = tempSum;
        }

        return max;
    }

    public static void main(String[] args) throws IOException {
        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());
        st = new StringTokenizer(br.readLine());
        int [] arr = new int[N];
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(N, M, arr));
    }
}

 

두 번째 코드(슬라이딩 윈도우)

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

public class sec03_03 {
    public static int solution(int N, int K, int[] arr) {
        int tempSum = 0;
        for(int i = 0; i < K; ++i) tempSum += arr[i];
        int max = tempSum;

        for(int i = K; i < N; ++i)
        {
            tempSum += (arr[i] - arr[i - K]);
            if(tempSum > max) max = tempSum;
        }

        return max;
    }

    public static void main(String[] args) throws 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());
        st = new StringTokenizer(br.readLine());
        int [] arr = new int[N];
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(N, K, arr));
    }
}

 

설명

두 번째 코드(슬라이딩 윈도우) 에대한 설명

• tempSum을 0으로 초기화하고, 첫 번째 for 루프에서 배열의 첫 번째 K개의 요소의 합을 계산하여 tempSum에 저장한다.
• 초기 최대값 max를 첫 윈도우의 합인 tempSum으로 설정한다.
• 두 번째 for 루프에서는 슬라이딩 윈도우 기법을 사용하여 다음 요소를 더하고, 이전 요소를 빼서 새로운 윈도우의 합을 구한다. 이 합이 max보다 크면 max를 갱신한다.