투포인터 (Two Pointers)

배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법

두 개 포인터의 배치 방법

 

- 같은 방향에서 시작 : 첫 번째 원소에 둘다 배치

- 서로 다른 방향에서 시작 : 첫 번째 원소와 마지막 원소에 배치

다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있음

 

sum의 값이 5보다 작다면, end를 1 늘려준다.

 

sum의 값이 여전히 5보다 작으니 end를 1 늘려준다.

 

 

sum의 값이 5보다 크니, start를 빼주고 값을 늘려준다.

 

 

sum의 값이 5와 같아져서 cnt를 1 올려주고, start와 end를 둘 다 올려준다.

 

 

sum의 값이 5와 같아져서 cnt를 1 올려주고, start와 end를 둘 다 올려준다.

 

 

 

sum이 5보다 크니, start를 빼주고 옆으로 움직인다.

 

sum의 값이 5와 같으니 cnt를 늘려준다

 

백준 2003 문제

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

public class baeckjoon_2003 {
    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());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st2.nextToken());
        }

        int sum = 0;
        int start = 0, end = 0, count = 0;

        while(true){
            if(sum >= m){
                sum -= arr[start++];
            }
            else if(end == n){
                break;
            }else{
                sum += arr[end++];
            }

            if(sum == m){
                count++;
            }
        }
        System.out.println(count);
    }
}