코딩테스트/기초

28. 연속 부분수열

누리는 귀여워 2024. 12. 20. 00:22

import java.util.*;

class Main {	
    public int solution(int n, int m, int[] arr) {
        int answer = 0, sum = 0, lt = 0;
        for(int rt = 0; rt < n; rt++) {
            sum += arr[rt];
            if(sum == m) {
                answer++;
            }
            // 합계가 m보다 높으면
            while(sum >= m) {
            	// 배열 0부터 출발한 lt의 값을 빼고 ++
                sum -= arr[lt++];
                if(sum == m) {
                    answer++;
                }
            }
        }
        return answer;
    }

	public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.print(T.solution(n, m, arr));
	}
}

1. rt는 오른쪽으로 이동하면서 sum에 값 누적

2. sum이 m보다 높으면 while문으로 이동

3. sum에 rt의 값을 빼고 m과 같으면 answer++

4. lt, rt가 한칸씩 이동하면서 m과 같은지 확인하면 됨

 

import java.util.*;

class Main {    
    public int solution(int n, int m, int[] arr) {
        int answer = 0, sum = 0, 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 kb = new Scanner(System.in);
        int n = kb.nextInt();
        int m = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.print(T.solution(n, m, arr));
    }
}