알고리즘) 연속부분수열

 N개의 수로 이루어진 수열이 주어지면, 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 문제이다.

 

초기 작성 코드

import java.util.Scanner;

public class Main {
    private int solution(int n, int m, int[] arr) {
        int answer = 0;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum == m) {
                    answer++;
                    break;
                } else if (sum > m) break;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
       	Main al = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

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

 내 힘만으로 작성한 코드는 이중 for문을 이용해 첫 인덱스를 계속해서 하나씩 증가시켜가며 해당 인덱스에서 시작하는 연속부분수열을 확인하는 방식으로, 수열의 길이가 길어지면 Time Limit이 발생할 여지가 많은 코드였다.

 

개선 코드 (1) - two pointer 알고리즘 방식

import java.util.Scanner;

public class Main {
    private int solution(int n, int m, int[] arr) {
        int answer = 0, lt = 0;
        int sum = 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 al = new Main();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

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

 개선된 코드는 두 개의 포인터(lt, rt)를 두어 마지막 인덱스 역할의 rt를 계속해서 증가시키면서 (-> 메인 루프의 인덱스로 삼음) sum의 값이 M보다 크고 작은 경우에 따라 양 포인터의 인덱스를 증가시키는 방식이다. sliding window와 유사한 듯하면서 범위를 고정시키지 않고 유동적으로 변경한다고 느껴진다.

 

개선 코드 (2) - 수학적 방법

import java.util.Scanner;

public class Main {
    private int solution(int num) {
        int answer = 0;

        // 두 번째 방식(수학적 방식)
        int cnt = 1;
        num--; // 연속 1 번째 수에 1 부여
        while (num > 0) {
            cnt++; // 2, 3, 4, ... 부여(연속 m 번째 수)
            num = num - cnt; // 2, 3, 4, ... 개의 수로 나누어 떨어지는지 여부 확인
            if (num % cnt == 0) answer++;

        }

        return answer;
    }

    public static void main(String[] str) {
        Main al = new Main();
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();
        System.out.println(al.solution(num));
    }
}

 연속되는 자연수는 모두 1씩 증가하는 수라는 점을 이용한 방식이다. m개의 자연수로 나누어 떨어지는지 알고자하면, 1부터 m까지의 수를 더한 만큼을 확인하려는 수에서 빼고, 나머지가 m으로 나누어 떨어지는지를 확인하면 된다. 즉, 나누어 떨어지는 경우에는 나누어 떨어지는 몫과 연속되는 수들의 나머지가 1 ~ m 처럼 연속적으로 증가하는지를 확인하는 방법이다. 세상에..