[백준/java] 1806번: 부분합 - 투 포인터 활용

https://www.acmicpc.net/problem/1806

1806번: 부분합

 

1806번: 부분합

728x90

코딩테스트 강의를 들으며 투 포인터를 익혔다.

 

강의에서도 부분수열의 합에 대해서 다뤘었는데 확실히 개념을 익히고 나니까 이번 문제를 풀 수있었다.

 

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

해당 강의 링크는 위와 같다

 

반응형

 

for문으로 돌면서 우측 포인터로 지정, int형 변수 lt를 선언하여 왼쪽포인터를 지정한다.

 

부분 수열의 합이 S가 넘으면 왼쪽 포인터의 값을 빼주고, 길이도 빼주면서 최솟값도 같이 구한다.

 

package twoPointer;

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

/**
 * 
 * 백준 : 1806번 부분합
 * https://www.acmicpc.net/problem/1806
 */

public class PartSum {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = stoi(st.nextToken());
		int S = stoi(st.nextToken());
		int min = Integer.MAX_VALUE;

		int[] arr = new int[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			arr[i] = stoi(st.nextToken());
		}
		
		int lt = 0, sum = 0, len = 0;
		for (int rt = 0; rt < N; rt++) {
			sum += arr[rt];
			len++;
			if(len > 1) {
				while(sum >= S) {
					min = Math.min(min, len);
					sum -= arr[lt++];
					len--;
				}
			}
		}
		
		if(min == Integer.MAX_VALUE) min = 0;
		System.out.println(min);
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}