[Algorithm] 연속 부분수열

연속 부분수열

설명

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

8 6
1 2 1 3 1 1 1 2

예시 출력 1

3

---

해결

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

public class Main {
    public int solution(int n, int m, int[] arr) {
        int answer=0, pos=0, sum=0; // pos는 포인터
        for (int i=0; i<n; i++) {
            sum += arr[i];
            // m에 대한 부분수열을 찾은 경우!
            if (sum == m) {
                answer++;
            }
            // sum이 m보다 크거나 같으면, 포인터를 활용해 배열의 인덱스를 하나씩 밀어가면서 다시 sum을 구한다
            // 큰 경우는 sum을 다시 구하기 위해서이고, 같은 경우는 m에 대한 다른 부분수열을 찾기 위함이다.
            while (sum>=m) {
                sum -= arr[pos++];
                if (sum == m) answer++;
            }
        }

        return answer;
    }

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        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());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i=0; st.hasMoreTokens(); i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(T.solution(N, M, arr));
    }
}

• 투 포인터 알고리즘과, 슬라이딩 윈도우 알고리즘으로 해결한 문제이다.
  • 투 포인터 알고리즘 사용을 위해 for문의 i와 pos변수가 사용되었다.
  • 슬라이딩 윈도우 알고리즘 사용을 위해 while문을 통해 왼쪽 포인터를 증가시켜 배열의 범위를 조정하며 답을 구했다.

---

삽질

public int solution(int n, int m, int[] arr) {
    int answer=0, pos=0, sum=0; // pos는 포인터
    for (int i=0; i<n; i++) {
        sum += arr[i];
        // sum이 m보다 크면, 포인터를 활용해 배열의 인덱스를 하나씩 밀어가면서 다시 sum을 구한다
        if (sum > m) {
           sum -= arr[pos++];
        }
        // sum이 m이면 answer++하고, 포인터로 인덱스를 하나 민다 (다른 경우 찾기 위해)
        if (sum == m) {
            answer++;
            sum -= arr[pos++];
        }
    }

    return answer;
}

• 수행결과가 예시의 정답과 같지만 계속 오답이었다.
• 예시의 기준만 생각했고, 더 다양한 경우를 생각하지 못해서 오답만 나왔던 거 같다