"투 포인터 알고리즘" + [백준] 2003 - 수들의 합 2(JAVA)

[문제]

출처 - https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

---

[문제 풀이 전]

N <= 10000 으로 나와 시간복잡도 해결을 하지 못했을 경우가 높을 것이다.

이 문제를 풀기 위해서는 '투 포인터' 라는 알고리즘을 알고 있어야 한다.

 

투포인터(Two Pointers)

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 선형 공간을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2)이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있는 알고리즘

만약, 정수로 이루어진 배열에서 연속된 부분 배열의 합이 특정 값(Target)을 이루는 부분 배열의 개수를 구하는 문제가 있다고 가정했을 때, 두 포인터 변수의 이동 조건은 다음과 같습니다.

 

(1) 부분 배열의 합이 Target 값보다 크거나 같으면  Left = Left + 1 해줍니다. (부분 배열의 길이를 줄여 합을 빼준다. )

if(sum >= Target) Left++;

(2) 부분 배열의 합이 Target 값보다 작으면 Right = Right + 1 해줍니다. (부분 배열의 길이를 늘려 합을 더한다.)

if(sum < Target) Right++;

(3) 부분 배열의 합이 Target 값과 같다면 결과 값을 +1 해줍니다. 

if( sum == Target) count++;

 

---

[문제 풀이]

위에서 설명한 그대로 소스코드를 구현을 하면 된다.

 

---

[소스 코드]

 

import java.io.*;
import java.util.*;

public class Main {

	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 s = Integer.parseInt(st.nextToken());
		int a[] = new int[n+1];
        
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		int sum=0;
		int left=0;
		int right=0;
		int ans = 0;

		while(right <= n) {
			if(sum >= s) {
				sum -= a[left++];
			}else if(sum < s) {
				sum += a[right++];
			}
			if(sum == s) ans++;
		}
		
		System.out.println(ans);

	}

}

 

이 문제를 풀 수 있다면 골드의 문제지만 아래의 문제도 쉽게 해결 할 수 있다.

 

백준(1806) - 부분합 ---> 문제 풀이

백준(1644) - 소수의 연속합 ---> 문제 풀이       

 

---

출처: https://bbangson.tistory.com/72 [뺑슨 개발 블로그]