백준 1806 부분합 [자바]

05 Jun 2022 in Develop / Solving

baekjoon 1806 부분합

java

문제 분석

• 10000 이하의 수로 이루어진 N개의 수열
• 이 중 연속된 수들의 부분합 중 합이 S이상 되는 것 중, 가장 짧은 것의 길이를 구하라.

입력조건

수 N, 합 목표 S
N개의 수

풀이과정

• 투포인터를 이용.
• 맨 왼쪽 인덱스에 두개의 포인터를 놓은 뒤,
• 현재 합이 목표보다 작다면 오른쪽 포인터를 하나 뒤로 밀고, 그 때 의 값을 부분합에 더함.
• 현재 합이 목표보다 크다면, 부분합에 사용된 숫자의 수를 체크하고, 왼쪽 포인터를 하나 뒤로 밈.
• 위의 과정을 왼쪽 포인터가 끝까지 도달하거나, 하나의 숫자로 답을 만들 수 있을 때까지 진행.

코드 구성

• 투 포인터

  while(r < N-1) {
      if(sum < S) { sum += map[++r]; }
      else 		{ sum -= map[l++]; }
      if(sum >= S) {
          ans = Math.min(ans, r-l+1);
    
          if(ans == 1) {
              System.out.println(1);
              return;
          }
      }
  }
  while(sum >= S && l < r) {
      sum -= map[l++];
      if(sum >= S) {
          ans = Math.min(ans, r-l+1);				
      }
  }
  

전체 코드

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

public class BJ1806_부분합 {
	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[] map = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int l = 0;
		int r = 0;
		int sum = map[0];
		if(sum >= S) {
			System.out.print(1);
			return;
		}
		int ans = Integer.MAX_VALUE;
		
		while(r < N-1) {
			if(sum < S) { sum += map[++r]; }
			else 		{ sum -= map[l++]; }
			if(sum >= S) {
				ans = Math.min(ans, r-l+1);
				
				if(ans == 1) {
					System.out.println(1);
					return;
				}
			}
		}
		while(sum >= S && l < r) {
			sum -= map[l++];
			if(sum >= S) {
				ans = Math.min(ans, r-l+1);				
			}
		}
		System.out.print(ans == Integer.MAX_VALUE ? 0 : ans);
	}
}