백준 1806: 부분합(Java, Javascript)

문제링크 : https://www.acmicpc.net/problem/1806

문제

문제를 해결한 방법

저는 투포인터를 이용해서 풀었습니다.

1. left=0, right=0 에서 시작합니다.
2. sum 이 S 보다 작으면 right를 1 증가시키고 sum에 더해줍니다.
3. sum 이 S 보다 크거나 같으면 left 인덱스의 값을 sum에서 빼주고 left를 1 증가시킵니다.
4. left와 right가 교차하거나 right가 배열 길이를 넘어갈 때까지 1~3을 반복

소스 코드(Java)

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

public class Main_1806_부분합 {

  public static void main(String[] args) throws Exception{
    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[] numbers = new int[N];

    st = new StringTokenizer(br.readLine());
    for(int i=0;i<N;i++) {
    numbers[i] = Integer.parseInt(st.nextToken());
    }

    int left = 0;
    int right = 0;
    int sum = numbers[0];
    int INF = Integer.MAX_VALUE;
    int min = INF;

    while(left <= right && right < N) {
      if(sum >= S) {
      int length = right - left +1;
      min = Math.min(min, length);
      }

      if(sum < S) {
        if(right + 1 >= N) break;
        sum += numbers[++right];
      }else {
        sum -= numbers[left++];
        }
      }

      if(min == INF) {
        System.out.println(0);
      }else {
        System.out.println(min);
      }
  }
}

소스 코드(Javascript)

const fs = require('fs');
const inputs = fs.readFileSync('./dev/stdin').toString().split("\n");

function main() {
  const [N, S] = inputs[0].split(" ").map(v => +v);
  const numbers = inputs[1].split(" ").map(v => +v);
  const MAX_NUMBER = 100001;
  let left = 0;
  let right = 0;
  let sum = numbers[0];

  let min = MAX_NUMBER;
  while (left <= right) {
    if (sum >= S) {
      min = Math.min(min, right - left + 1);
    }

    if (sum < S) {
      if (right + 1 === N)
        break;
      sum += numbers[++right];
    } else {
      sum -= numbers[left++];
    }
  }
  if (min === MAX_NUMBER) {
    console.log(0);
  } else {
    console.log(min);
  }
}

main();