[투포인터] 연속 부분수열 .java

설명

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

 

 

내 풀이

인덱스 0부터 연속되는 합이 m과 같은 경우의 수를 세는 문제이다

n의 최댓값 = 100,00 => O(n^2)으로 풀지 말아야 함

 

1. for문으로 배열을 처음부터 끝까지 탐색 -> 앞부터 하나씩 더하기

2. 더한 sum 값이 m보다 커지면 현재 수열에서 맨 처음 값을 빼준다 -> cnt 변수 활용

=> 포인트는 한 번만 빼주지 말고 sum값이 m보다 같거나 작아질 때까지 계속 빼야 한다 

 이 부분을 생각 못하고 if문으로만 하니 결과가 이상하게 나왔다

3. 2번 과정을 거친 후 m값이면 경우의 수를 찾았기 때문에 정답 증가

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        int answer = 0;

        int sum = 0;//현재 연속 부분 수열의 합
        int cnt = 0;//연속부분수열의 시작 인덱스

        for(int i = 0; i < n; i++){
            sum += arr[i];//현재 i 값까지의 총합

            //sum이 목표 합 m보다 클 경우 시작 인덱스를 이동하며 합을 줄임
            while (sum > m) {
                sum -= arr[cnt];//현재 수열의 첫 번째 값 빼기
                cnt++;//시작 인덱스 증가

            }
            if(sum == m) answer++;//같으면 정답 증가
        }
        System.out.print(answer);

    }
}

 

 

다른 풀이

1. rt, lt의 두 개의 포인터 사용 => lt ~ rt의 합을 구함 (총합 sum 변수)

2. 연속된 수열을 합한 값(sum)이 m과 같은지 검사

3. sum < m : rt 증가  -> 증가한 rt 값 총합에 더함 => m과 같은지 검사

4. sum  >=  m : lt의 값을 총합에서 빼기 -> lt 증가  => m과 같은지 검사  

 

나와 다른 점은 while문 안에서 m과 동일 값인 경우를 처리하느냐가 다르다

 

import java.util.Scanner;

public class Main {
    public int solution(int n, int m, int[] arr){
        int answer = 0;
        int sum = 0;
        int lt = 0;

        for(int rt = 0 ; rt < n; rt++){
            sum += arr[rt]; //먼저 더하기
            if(sum == m) answer++;
            while(sum >= m) {
                sum -= arr[lt++];
                if(sum == m) answer++;
            }
        }


        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }


        System.out.print(T.solution(n,m,arr));

    }
}

 

 

💡💡

처음엔 어떻게 풀어야 할지 막막했는데 연속된 수열이 포인트였던 문제다