[인프런] 03_04 연속 부분 수열 (Two pointers)

📖  문제

---

• 첫째 줄 N, 특정 숫자 M이 주어진다.
• 둘째 줄에는 N개의 수로 이루어진 수열이 주어진다.
  • 수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하시오
• N = 8, M = 6인 경우 아래와 같은 배열을 가지면 3가지 입니다.
  • {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}

출력 예시

 

⚠️  주의사항

---

• Two pointers 알고리즘 풀 때 한 개의 배열일 때는 어떻게 해야 할지
• 수열의 마지막을 벗어나지 않게 조심하기

2022.01.21 - [인프런_자바_알고리즘_기초/Two pointers, Sliding window] - 투 포인터란?

 

✍️  이해

---

* 1. N개의 배열 M이 되는 경우
* 2. 투 포인터 방식으로 left, right 변수 선언
*  2-1. sum = left ~ right 사이 배열 합
*  2-2. M > sum -> sum += N[++right]
*  2-3. M < sum -> sum -= N[left++]
*  2-4. M == sum -> answer ++,  sum -= N[left++]
* 3. N == sum -> answer++ 마지막 값까지 확인해주기.
* 4. retrun answer;

 

✏️  풀이

---

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

public class Java03_04 {

    public int solution(int N, int M, int[] arr) {

        int answer = 0, sum = 0;
        int left = 0, right = 0;

        sum = arr[left];
        while (right < N - 1) {

            if (M > sum) sum += arr[++right]; // right를 오른쪽으로 한 칸 옮기고 그 값을 sum에 누적
            else if (M < sum) sum -= arr[left++]; // 왼쪽 한 칸을 sum 값에서 빼고 left를 오른쪽으로 한 칸 이동
            else { // M = sum
                sum -= arr[left++]; // 같은 값의 경우에도 왼쪽 한 칸을 sum 값에서 빼고 left를 이동
                answer++; // answer 값 누적
            }
        }

        if (M == sum) answer ++; // 마지막 값 확인

        return answer;
    }

    public static void main(String[] args) throws IOException {

        Java03_04 T = new Java03_04();

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

        System.out.println(T.solution(N, M, arr));
    }
}

---

출력화면