자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(sliding window_최대 매출)

 

https://cote.inflearn.com/contest/10/problem/03-03

OnlineJudge

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

 

 

3. 최대 매출

 

예시 입력 1 

10 3
12 15 11 20 25 10 20 19 13 15

예시 출력 1

56

 

 

내가 푼 틀린 풀이 (Time: 1519ms Memory: 34MB) - Time Limit Exceeded

 

강의에서 보니까 이중 반복문으로 풀면 시간 초과가 나와서 절대 그렇게 풀지 말라고 한다.

내가 그렇게 풀었다.

p1부터 p2까지 배열의 구간 합으로 구해야 되는 줄 알았는데, 2중 반복문을 쓰면 안된다고 한다!!

구간합이 아니라 슬라이딩 윈도우로 풀어야 한다!!!

import java.util.Scanner;

public class Main {
    // Time Limit Exceeded 실패
    public int solution(int a, int b, int[] arr) {
        int p1 = 0, p2 = p1 + (b-1);
        int max = Integer.MIN_VALUE;
        while (p2 < arr.length) {
            int sum = 0;
            for (int i = p1; i <= p2 ; i++) {
                 sum += arr[i];
            }
            max = Math.max(max, sum);
            p1++;
            p2++;
        }

        return max;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int[] arr = new int[a];
        for (int i = 0; i < a; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(T.solution(a, b, arr));
    }
}

 

 

강의 풀이(Time: 785ms Memory: 35MB)

n이 10만개의 자료가 들어오는데, k가 5만일 경우, 100,000 x 50,000이 되어버려서 너무 복잡도가 커진다.

10만만 돌면 되도록 코드를 짜야 합니다 O(n)

슬라이딩 윈도우가 무엇인가하면, 창문을 만들어서 옆으로 밀고 쭈욱 가면 됩니다.

1. 최초에 0부터 k2전까지 돌면서 미리 합을 구해놓아야 합니다.

2. 한 칸 밀어야 하는데, 이제 i가 인덱스 3번부터 돌면 되는데, sum에 arr[i]를 더하고, arr[i-k]를 빼줍니다.

그렇게 되면 38이 46이 됩니다. 이런식으로 창문을 옆으로 옮기면서 계속 계산해주면 됩니다.

import java.util.Scanner;

public class Answer {

    public int solution(int n , int k, int[] arr) {
        int answer = 0, sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i]; // 초반에 sum을 구해줍니다.
        answer = sum; // 최대값 구하기 위한 초기 세팅

        for (int i = k; i < n; i++) { // 윈도우로 밀고 가는 부분
            sum += (arr[i] - arr[i-k]); // 음수가 될지 양수가 될지는 모르지만 누적해줌
            answer = Math.max(answer,sum);
        }
        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n ; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n,k,arr));
    }
}

 

 

슬라이딩 윈도우 예제 코드

• 주어진 배열 또는 문자열에서 고정 크기의 창(윈도우)를 이용하여 문제를 해결하는 알고리즘입니다.
• 이 알고리즘은 주로 연속적인 부분 배열 또는 부분 문자열의 합, 최대 값, 최소 값 등을 효율적으로 계산할 때 사용됩니다. 

 

배열에서 연속된 k개의 요소의 최대 값을 찾는 코드 예제입니다. 현재 윈도우 내에서 최대 값을 찾기 위해 윈도우의 첫 번째 요소를 초기 최대 값으로 설정하고, 나머지 요소를 순회하면서 최대 값을 찾습니다.

 

public class SlidingWindowMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] result = new int[n - k + 1]; // 결과 배열의 길이
        int resultIndex = 0;

        for (int i = 0; i <= n - k; i++) {
            int maxInWindow = nums[i]; // 윈도우 내의 첫 번째 요소를 최대 값으로 초기화

            // 현재 윈도우 내에서 최대 값을 찾음
            for (int j = i + 1; j < i + k; j++) {
                maxInWindow = Math.max(maxInWindow, nums[j]);
            }

            result[resultIndex] = maxInWindow;
            resultIndex++;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = maxSlidingWindow(nums, k);

        System.out.println("슬라이딩 윈도우의 최대 값:");
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}