자바 알고리즘 문제 풀이 입문. 섹션3. Two Pointers, Sliding Window [효율성 : O(n^2) --> O(n)] : 연속 부분수열

 

https://hyejin.tistory.com/1222

자바 알고리즘 문제 풀이 입문. 섹션3. Two Pointers, Sliding Window [효율성 : O(n^2) --> O(n)] : 최대 매출

-> 이전 문제 풀이 

 

 

 

4. 연속 부분수열 

설명

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가지입니다.

 

입력

첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.

수열의 원소값은 1,000을 넘지 않는 자연수이다.

 

출력

첫째 줄에 경우의 수를 출력한다.

 

예시 입력 1 

8 6
1 2 1 3 1 1 1 2

 

예시 출력 1

3

 

 

문제 풀이 1

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

    for (int i = 0; i < n; i++) {
        sum = arr[i];
        for (int j = 1; j <= n - i-1; j++) {
            sum += arr[i + j];
            if (sum == m) {
                answer++;
                break;
            } else if (sum > m) {
                break;
            }
        }
    }
    return answer;
}

👩🏻‍💻 : 이 문제도 보고 이중 for 문 말고 어떻게 풀지 감이 안와서 그냥 내 식대로 한번 풀어봤다. 

대신 최대한 시간 초과 안되도록 풀어봤는데 이번에는 시간 초과 안걸리고 정답이었다 ! 

 

두번째 for문을 돌 때 n 만큼 다 도는게 아니라 i 에 더할 값을 구해줬다. 즉 i = 1 이면 i + 1 ~ i + 7 까지 , i = 2 이면 i + 1 ~ i + 6 까지.. 

이런식으로 해서 sum 에 누적해서 더하는데 이때 sum 이 주어진 m 값과 같으면 answer에 +1 해주고, 더이상 반복문 돌 필요가 없으니 break 해주고, m보다 sum의 값이 커지면 역시 더이상 반복문 돌며 더할 필요 없으므로 break 해준다. 

 

 

 

문제 풀이 2

public int solution2(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;
}

👾 : 이 풀이는 강사님이 푼 방식이다. 먼저 lt , rt 변수를 만들고, sum으로 arr[0] 부터 arr[n-1]까지 더하는데 이때 이 값이 m 과 같으면 answer에 +1 해준다. 근데 sum이 m 보다 크거나 같으면 arr[lt] 값을 sum에서 빼준다. (맨 왼쪽 배열 값을 빼주는 것) 그 다음 lt 값을 1 증가해준다. 다음 이 sum 값이 m 과 같으면 answer 에 +1 해주고, m 보다 여전히 크다면 arr[lt] 값을 더해준다. 만약 m 보다 작아지면 다시 arr[rt] 값을 더하고 비교한다 .

 

즉, 우선 더하고 비교하고 빼고 비교하고.. 이렇게 반복하는 것이다.