투포인터
- 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하며 처리하는 알고리즘이다.
문제와 코드를 통해서 알아보겠다
- 백준 (2003번) 수들의 합 2
문제
N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
풀이
package TwoPointer; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class NumberSum2 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); // 투포인터 -> head tail -> 중견기업 단골 문제다 // 1초 -> 몇번 컴퓨터가 10억 // int -> 21억 int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] number = new int[n]; int ans = 0; st = new StringTokenizer(br.readLine(), " "); for (int i = 0; i < n; i++) number[i] = Integer.parseInt(st.nextToken()); int left = 0; int right = 0; int sum = 0; // 투포인터인 이유 -> 슬라이딩 윈도우 -> while (left <= right) { if (sum >= m) { sum -= number[left]; left++; } else if (right >= n) { break; } else { sum += number[right]; right++; } if (sum == m) ans++; } // head : 4 tail :6 -> 6 System.out.println(ans); } }