Algorithm/Two Pointer
투 포인터 - BOJ - 1806 부분합
Lazy_developer
2023. 3. 19. 20:59
문제
https://www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
문제 접근
- 앞서 해보았던 투 포인터 유형의 대표적인 문제인 부분합 / 구간 찾기 문제이다.
- 문제를 상세히 읽어보면 부분합이 S이상이 되면 되므로 $S_{cur} \geq S_{target}$ 를 만족하게 되면 left를 하나씩 올리면서 위 구간합이 만족하는지를 검사하며 구간을 줄여나가면 된다.
- 만약 $S_{cur} < S_{target}$ 라면 right를 움직여서 다음 요소를 더하도록 하면 된다. 이상이라는 말에 주목하면 나머지는 투 포인터 구현의 기본적인 문제였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] data = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++){
data[i] = Integer.parseInt(st.nextToken());
}
int ans = 100000;
int start = 0;
int end = 0;
int sum = 0;
while(true){
if (sum >= S){
int distance = end - start;
ans = Math.min(ans, distance);
sum -= data[start++];
} else if (end == N){
break;
} else {
sum += data[end++];
}
}
if (ans == 100000){
System.out.println(0);
} else{
System.out.println(ans);
}
}
}
- 구현하면서 느꼈던건 end의 경우, 순서를 잘못하면 ArrayOutOfBounds 가 뜰 수 있다. 반드시 end의 길이 체크를 끝낸 뒤에 end를 올리도록 하는게 중요하단 것이었다.