[Algorithm] Sliding window

시간 복잡도를 O(n^2)에서 O(n)으로 바꿀 수 있는 Sliding window 알고리즘을 활용하여 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.

---

최대 매출

현수의 아빠는 제과점을 운영합니다. 현수아빠는 현수에게 N일 동안의 매출기록을 주고 연속 된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 15 (11 20 25) 10 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요.

• 입력설명
  첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
  두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
• 출력설명
  첫 줄에 최대 매출액을 출력합니다.
• 입력예제 1
  10 3
  {12 15 11 20 25 10 20 19 13 15}
• 출력예제 1
  56

public class BiggestSales {

    public int solution1(int[] inputs, int totalDays, int targetDays) {
        int answer = 0;
        int sum = 0;
        for (int i = 0; i < targetDays; i++) {
            sum += inputs[i];
        }
        for (int i = targetDays; i < totalDays; i++) {
            sum += inputs[i] - inputs[i - targetDays];
            answer = Math.max(answer, sum);
        }
        return answer;
    }

    @Test
    @DisplayName("최대 매출")
    public void main() {
        int[] inputs = {12, 15, 11, 20, 25, 10, 20, 19, 13, 15};
        int totalDays = 10;
        int days = 3;
        int answer1 = solution1(inputs, totalDays, days);
        assertEquals(56, answer1);
    }

}

---

연속 부분수열

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
1 2 1 3 1 1 1 2
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

• 입력설명
  첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다. 수열의 원소값은 1,000을 넘지 않는 자연수이다.
• 출력설명
  첫째 줄에 경우의 수를 출력한다.
• 입력예제 1
  86
  {1 2 1 3 1 1 1 2}
• 출력예제 1
  3

public class ContinuousSequencePart {

    public int solution1(int length, int sum, int[] arr) {
        int answer = 0;
        int p1 = 0;
        int p2 = 0;
        int tmpSum = 0;
        while (p1 < length && p2 < length) {
            if (tmpSum == sum) {
                answer++;
                tmpSum -= arr[p1++];
            } else if (tmpSum > sum) {
                tmpSum -= arr[p1++];
            } else {
                tmpSum += arr[p2++];
            }
        }
        return answer;
    }

    public int solution2(int length, int sum, int[] arr) {
        int answer = 0;
        int tmpSum = 0;
        int p1 = 0;
        for (int p2 = 0; p2 < length; p2++) {
            tmpSum += arr[p2];
            if (tmpSum == sum) {
                answer++;
            }
            while (tmpSum >= sum) {
                tmpSum -= arr[p1++];
                if (tmpSum == sum) {
                    answer++;
                }
            }
        }
        return answer;
    }

    @Test
    @DisplayName("연속 부분수열")
    public void main() {
        int[] inputs = {1, 2, 1, 3, 1, 1, 1, 2};
        int length = 8;
        int sum = 6;
        int expectedAnswer = 3;
        int answer1 = solution1(length, sum, inputs);
        assertEquals(expectedAnswer, answer1);
        int answer2 = solution2(length, sum, inputs);
        assertEquals(expectedAnswer, answer2);
    }

}

---

최대 길이 연속 부분 수열

0과 1로 구성된 길이가 N인 수열이 주어집니다. 여러분은 이 수열에서 최대 k번을 0을 1로 변경할 수 있습니다.
여러분이 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 작성하세요.
만약 길이가 길이가 14인 다음과 같은 수열이 주어지고 k=2라면 11001101101101
여러분이 만들 수 있는 1이 연속된 연속부분수열은 1 1 0 0 [1 1 1 1 1 1 1 1] 0 1 이며 그 길이는 8입니다.

• 입력설명
  첫 번째 줄에 수열의 길이인 자연수 N(5<=N<100,000)이 주어집니다. 두 번째 줄에 N길이의 0과 1로 구성된 수열이 주어집니다.
• 출력설명
  첫 줄에 최대 길이를 출력하세요.
• 입력예제 1
  14 2
  {1 1 0 0 1 1 0 1 1 0 1 1 0 1}
• 출력예제 1
  8

public class MaxLengthContinuousSequence {

    public int solution1(int length, int change, int[] arr) {
        int answer = 0;
        int count = 0;
        int p1 = 0;
        for (int p2 = 0; p2 < length; p2++) {
            if (arr[p2] == 0) {
                count++;
            }
            while (count > change) {
                if (arr[p1] == 0) {
                    count--;
                }
                p1++;
            }
            answer = Math.max(p2 - p1 + 1, answer);
        }
        return answer;
    }

    @Test
    @DisplayName("최대 길이 연속부분수열")
    public void main() {
        int length = 14;
        int change = 2;
        int[] arr = {1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1};
        int expectedAnswer = 8;
        int answer1 = solution1(length, change, arr);
        assertEquals(expectedAnswer, answer1);
    }

}

---

참고한 강의: https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84