[Java] 2003. 수들의 합 2

문제

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.io.*;

public class Main{
    public static void main(String args[]) throws IOException{
        // 입력
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String[] input=bf.readLine().split(" ");
        int n=Integer.parseInt(input[0]);   // 수열의 갯수
        int m=Integer.parseInt(input[1]);    // 합
        String[] lst=bf.readLine().split(" ");
        int[] a=new int[n];
        for(int i=0; i<n; i++){
            a[i]=Integer.parseInt(lst[i]);
        }

        int start=0, end=0, cnt=0, sum=0;
        while(true){
            if(sum >= m){
                sum-=a[start++];
            }else if(end==n){
                break;
            }else{
                sum+=a[end++];
            }

            if(sum == m){
                cnt++;
            }
        }

        System.out.println(cnt);

        }
        }

 

투포인터 풀이

첨에 while의 조건에 end<n이라고 했었는데 이렇게 하면 정답값보다 작을 수 있어서 적절하지 않다.

end가 마지막 인덱스더라도 start에 따라서 m을 만족하는 구간합이 더 있을 수 있음.

결국 while문이 종료되는 시점은 end가 마지막 인덱스고 구간합이 m 미만일 때다.

sum이 m이상이면 시작 범위 start의 값을 빼고 인덱스를 늘린다.

구간합sum이 m보다 작으면 계속 end를 증가시키면서 구간합을 늘린다.

start와 end 범위의 구간합이 m과 일치하면 경우의 수 cnt를 증가시킨다.

조건의 순서를 잘 따져야한다. sum==m이 앞으로 가거나 그러면 안됨..

 

 

💛 다른사람 풀이

 

// https://maivve.tistory.com/223
import java.io.*;
import java.util.StringTokenizer;

public class Main{
    public static void main(String args[]) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());

        st=new StringTokenizer(br.readLine());
        int[] arr=new int[n];

        for(int i=0; i<n; i++){
            arr[i]=Integer.valueOf(st.nextToken());
        }

        System.out.println(twoPointer(arr, m));
    }

    static int twoPointer(int[] arr, int m){
        int count=0;
        int startPoint=0, endPoint=0;
        int len=arr.length;
        int sum=0;

        while(true){
            if(sum >= m){
                sum-=arr[startPoint++];
            }else if(endPoint >= len){
                break;
            }else{
                sum+=arr[endPoint++];
            }

            if(sum == m){
                count++;
            }
        }
    return count;
    }
}

 

투포인터 풀이

함수를 따로 만들어서 구현함.

 

 

// https://log-laboratory.tistory.com/112
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long m=sc.nextLong();
        int[] arr=new int[n];
        for(int i=0; i<n; i++){
            arr[i]=sc.nextInt();
        }

        int count=0;
        long sum=0;
        int left=0, right=0;
        while(true){
            if(sum >= m){
                sum-=arr[left++];
            }else if(right==n){
                break;
            }else{
                sum+=arr[right++];
            }

            if(sum == m){
                count++;
            }
        }

        System.out.println(count);
    }
}

 

입력 받을 때 Scanner를 사용했다.

 

 

 

문제 출처 👉 백준