[문제풀이] 03-04. 연속 부분 수열

인프런, 자바(Java) 알고리즘 문제풀이

Two pointers, Sliding window - 0304. 연속 부분 수열

🗒️ 문제

🎈 나의 풀이

	private static int solution(int n, int m, String[] strArr) {
        int answer = 0, sum = 0, r = 0, l = 0;

        while(r < n && l < n) {
            if(sum > m) sum -= Integer.parseInt(strArr[l++]);
            else sum += Integer.parseInt(strArr[r++]);
            if(sum == m) answer++;
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc =  new Scanner(System.in);
        String[] strArr = sc.nextLine().split(" ");
        int n = Integer.parseInt(strArr[0]);
        int m = Integer.parseInt(strArr[1]);
        strArr = sc.nextLine().split(" ");

        System.out.println(solution(n, m, strArr));
    }

🖍️ 강의 풀이

    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));
	}

💬 짚어가기

해당 문제는 two pointers와 sliding window를 복합적으로 이용하여 풀 수 있다.
window의 시작과 끝 index를 두 개의 pointer가 가르키며, 각 pointer를 개별로 이동시켜
가변적인 크기의 window를 통해 배열을 탐색하는 것이다.

핵심은 pointer를 이동시키는 조건을 어떻게 줄 것인가이다.