[JAVA] 백준 2003번- 수들의 합

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] arr = new int[n];

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

        int left = 0, sum = 0, cnt = 0;
        for(int right = 0; right< n; right++){
            sum += arr[right];
            if(sum == m) cnt++;
            while(sum>=m){
                sum-=arr[left++];
                if(sum==m) cnt++;
            }
        }
        System.out.println(cnt);
    }
}

 

0번째 인덱스부터 끝 인덱스까지 n번
1번째 인덱스부터 끝까지 n-1번
2번째 인덱스까지 n-2번 
.
.
.

이런식으로 확인하면 시간복잡도가 O(n^)이 된다.

 

투포인터 알고리즘을 이용해 O(n)으로 줄일 수 있다. 

 

sum이 m보다 작을 때는 right 를 증가시키고, 

sum이 m과 같거나 클 때는 left를 증가시켜 left와 right 사이의 숫자들의 합을 구한다.

 

이 때, left의 이동횟수 n번 + right의 이동횟수 n번 = 2n 이 되어 시간복잡도가 O(n)로 구할 수 있다. 

 

 

 

while문만 사용한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] nums = new int[n+1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int left= 0, right = 0, sum = 0, count = 0;
        sum = nums[0];

        while(true){
            if(sum==m){
                count++;
                sum-=nums[left++];
            }else if(sum > m){
                sum-=nums[left++];
            }else{
                sum+=nums[++right];
            }
            if(right == n) break;
        }
        System.out.println(count);
    }
}