[알고리즘] 백준 2003번: 수들의 합 2 (자바/Java) - 슬라이딩 윈도우, 구간합

스터디 중에 풀었던 알고리즘 문제 백준 2003번: 수들의 합 2 문제를 가져와봤다.

 

사실 이 문제는 투 포인터 기법을 활용해서 문제를 푸는 것 같았다.

 

하지만 오늘 스터디에서 투 포인터를 들어가기 전에 슬라이딩 윈도 기법을 먼저 진행했기 때문에 이번 문제는 슬라이딩 윈도 기법으로 풀어보았다.

 

 

 

문제는 다음과 같다.

---

수들의 합 2 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

0.5 초

128 MB

17563

8645

5801

50.752%

문제

N개의 수로 된 수열 A [1], A [2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A [N]이 공백으로 분리되어 주어진다. 각각의 A [x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1

4 2 1 1 1 1

예제 출력 1

3

예제 입력 2

10 5 1 2 3 4 2 5 3 1 1 2

예제 출력 2

3

---

정답 코드는 아래와 같다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int target = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }// 예제 입력 끝

        int result = 0; // 결과값 저장 변수

        // m : 슬라이딩 윈도우 - 몇개씩 탐색할 것인지..
        for(int m=0; m<n; m++) {
            int left = 0, right = m; // left부터 right까지: 윈도우의 범위 index
            int sum = 0; // 윈도우 범위의 부분합

            // 초기 sum값 세팅 -> 윈도우 범위만큼의 값을 최초에 가짐
            for(int i=0; i<=right; i++) {
                sum += arr[i];
            }
            if(sum == target) result++;
            right++;

            // right 인덱스의 범위가 n을 벗어나기 전까지 반복
            while(right < n) {
                // [윈도우] 의 다음 범위는 [윈도우] - arr[left] + arr[right] 임.
                sum -= arr[left++];
                sum += arr[right++];
                // target 값과 비교하여 같다면 result 값 1 증가
                if(sum == target) result++;
            }
        }
        System.out.println(result);
    }
}

 

윈도의 크기가 1부터 N개가 될때까지 슬라이딩 윈도우 기법을 적용하여 문제를 풀었다.

---

아래는 슬라이딩 윈도우 기법에 대한 이해를 돕기 위해 직접 만든 ppt이다.

 

 

참고하면 좋을 듯하다.

 

(숫자 예제는 임의의 숫자를 넣은 것임)

 

끝!

 

피드백은 언제든 댓글로 부탁드리겠습니다!!