[알고리즘] 3-4 연속 부분수열 - two pointers 알고리즘(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 간략한 문제 설명, 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/03-04
• 문제 설명 : n개의 수로 이루어진 수열이 주어졌을때, 연속부분수열의 합이 숫자 m이 되는 경우가 몇 번인지 구하는 문제

예습 풀이

• Two pointers 알고리즘을 사용하여 풀이
• 중복되는 코드가 신경 쓰인다

package inflearn.tow_pointers_sliding_window;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main3_4 {

    public static int solution(int n, int m, int[] arr) {
        int start = 0, end = 0, answer = 0, sum = 0;

        while (start < n) {

            if (end >= n) {
                start++;
                end = start;
                sum = 0;
                continue;
            }

            sum += arr[end];

            if (sum == m) {
                answer++;
                start++;
                end = start;
                sum = 0;
            } else if (sum > m) {
                start++;
                end = start;
                sum = 0;
            } else {
                end++;
            }
        }

        return answer;
    }

    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; st.hasMoreTokens(); i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

강의보고 복습 풀이

• 마찬가지로 two pointers 알고리즘 사용
• 예습 풀이와 비교하면 코드도 간결해보이고, 불필요한 반복 횟수가 줄어들었다.
  • 문제에서 주어진 입력 예시로 반복 횟수를 카운팅한 결과 반복 횟수 29 -> 12로 크게 감소

public static int solution2(int n, int m, int[] arr) {
    int answer = 0, sum = 0, left = 0;

    for (int right = 0; right < n; right++) {
        sum += arr[right];

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

        while (sum >= m) {
            sum -= arr[left++];
            if (sum == m) {
                answer++;
            }
        }
    }

    return answer;
}