설명

N개의 수로 이루어진 수열이 주어집니다.

이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.

만약 N=8, M=6이고 수열이 다음과 같다면

1 2 1 3 1 1 1 2

합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

코드

public class ContinueNumber {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int input2 = in.nextInt();
        int[] arr = new int[input1];

        for(int i=0; i<input1; i++){
            arr[i] = in.nextInt();
        }

        int solution = solution2(arr, input2);
        System.out.println(solution);
    }
    public static int solution(int[] arr, int target){
        int p = 0;
        int sum = 0;
        int range = 0;
        int cnt = 0;

        int length = arr.length;

        while(p < length){
            if(p+range>=length){
                p++;
                range = 0;
                sum = 0;
                continue;
            }
            sum += arr[p+range];
            if(sum<target){
                range++;
            }else if(sum == target){
                p++;
                range = 0;
                sum = 0;
                cnt++;
            }else{
                p++;
                range = 0;
                sum = 0;
            }
        }

        return cnt;
    }

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

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

solution은 내가 직접 풀이한 알고리즘인데 sliding window 알고리즘을 참고하여 왼쪽을 기준으로 값을 계속해서 더해나가 기준 값보다 작다면 한칸 더 전진 크다면 값을 확인하고 count를 증가시킬지 검사하는 방식이다. 이 방법으로도 정답 처리가 되었고 시간 복잡도 또한 O(N)으로 풀이에 문제는 없었으나 알고리즘이 한눈에 안들어온다는 단점이 있다.

solution2는 강사님이 풀이한 알고리즘이고 내가 생각한 기준과는 다르게 값을 기준으로 왼쪽에서 값을 줄여서 온다. 예를 들어

기준값이 6이고 주어진 배열 값이 1 1 1 1 5 라면 최초 sum의 값이 1부터 시작해서 2,3,4,5,9 이렇게 커져간다. 하지만 여기에 기준값 6에 해당하는 값이 없지만 while 조건에 sum값이 기준값보다 크기 때문에 왼쪽에서 값을 줄여서 검사하기 시작한다. 이제는 9부터 시작해서 8,7,6에서 기준 값이 6과 같으므로 count가 증가하고 그 다음 반복에서 sum의 값이 기준값보다 작아지므로 while을 탈출한다. 이런식으로 풀이를 할수도 있었다. 여기서 반복문이 2개인데 어떻게 O(N)이 될수 있나요? 라고 헷갈릴 수도 있는 부분인데. for문과 while문을 잘 살펴보면 for문은 rt값이 증가되어 계속 범위가 넓어지며 값이 커졌을 경우 lt가 커져서 왼쪽 범위는 계속 줄어든다. 이렇게 계속 반복되면 결국 프로그램 전체적으로는 O(N) 만큼 반복되어지는 것을 확인할 수 있다. 시간 복잡도 또한

아래가 solution이고 위가 solution2인데 오히려 더 빠른것을 확인할 수 있었다.

반복이 2중 반복이라고 무조건 O(N^2)이 아니다. 프로그램 전체적인 반복 횟수를 계산해보며 풀이하자