백준[JAVA] - 수들의 합 2 (2003)

 

---

이중 for 문으로 어렵지 않게 풀었던 것 같다 

import java.util.*;

public class Baekjoon2003 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] A = new int[N];
        int count = 0;

        for(int i = 0; i < N; i++){
            A[i] = sc.nextInt();
        }

        for(int i = 0; i < N; i++){
            int sum = 0;
            for(int j = i; j < N; j++){
                sum += A[j];
                if(sum == M){
                    count++;
                }

            }
        }
        System.out.println(count);
    }
}

하지만 풀고도 뭔가 찝찝한 마음에 검색을 해 봤다

 

역시  좀 더 효율적인 방법으로 풀 수 있었다

나는 모든 경우의 수를 돌리는 것이기 때문에 시가간복잡도가 O(N^2)이 된다 

 

하지만 투 포인터 알고리즘을 사용하면 O(N)의 시간 복잡도로 해결할 수 있다.

 

사용 방법은 start와 end라는 두 개의 포인터를 사용해서 배열을 스캔한다. 

sum 이 M 보다 크거나 같을 경우, start 포인터가 가리키는 값을 sum에서 빼고 start 를 한칸 이동한다. 

반대로 sum 이 M 보다 작을 경우, end 포인터가 가리키는 값을 sum에 더하고 end를 한칸 이동한다. 

 

 

package S4_Baekjoon;

import java.util.*;

public class Baekjoon2003 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt(); 

        int[] A = new int[N]; 
        int count = 0; 

        for(int i = 0; i < N; i++){ 
            A[i] = sc.nextInt();
        }

        int start = 0; // start는 부분합을 구성하는 숫자들의 시작 인덱스입니다.
        int end = 0; // end는 부분합을 구성하는 숫자들의 끝 인덱스입니다.
        int sum = 0; // sum은 부분합입니다.
        
        while(true) { // 부분합이 M보다 크거나, end가 배열의 끝에 도달할 때까지 반복합니다.
            if(sum >= M) { // 부분합이 M보다 크거나 같으면 start 위치의 숫자를 제외합니다.
                sum -= A[start++];
            } else if(end == N) { // end가 배열의 끝에 도달하면 반복을 종료합니다.
                break;
            } else { // 부분합이 M보다 작으면 end 위치의 숫자를 포함합니다.
                sum += A[end++];
            }
            
            if(sum == M) { // 부분합이 M과 같으면 count를 증가시킵니다.
                count++;
            }
        }

        System.out.println(count); // M을 만족하는 부분합의 개수를 출력합니다.
    }
}