백준 1806 nodejs

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

이분 탐색 사용

const sum = A.reduce((a, b) => a + b, 0)
let O = 0
if (sum >= S) {
  let [l, r] = [1, N]
  while (l < r) {
    const m = Math.floor((l + r) / 2)
    let sSum = 0
    for (let i = 0; i < m; i++) sSum += A[i]
    let max = sSum
    for (let i = m; i < N; i++) {
      sSum += A[i] - A[i - m]
      if (sSum > max) max = sSum
    } // 부분합의 최댓값 max를 구함
    max < S ? (l = m + 1) : (r = m)
  }
  O = r
}
console.log(O)

두 포인터 사용

const I = fs.readFileSync('/dev/stdin').toString().trim().split('\n')
const [[N, S], A] = [I[0].split(' ').map(Number), I[1].split(' ').map(Number)]
let l = (r = 0)
let [sum, O] = [A[0], N + 1]
while (sum) {
  if (sum < S) sum += A[++r]
  else {
    O = Math.min(O, r - l + 1)
    sum -= A[l++]
  }
} // r이 범위를 벗어나 sum이 NaN이 될 때까지 반복
if (O == N + 1) O = 0
console.log(O)

속도 비교

차례대로 두 포인터, 이분 탐색

결과 분석

두 풀이 모두 사용 가치 있음. 이분 탐색을 이용한 풀이가 직관적으로 떠올리기 쉬움. 코드 길이 측면에서는 두 포인터가 유리.