[백준 알고리즘] Node.js 1806. 부분합

1. 문제

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

1806번: 부분합

 

2. 풀이

1) 수열의 구간의 합을 구하여 주어진 S 이상의 값을 얻는 순간 배열의 길이를 구한다. 

2) 구한 길이 중 가장 짧은 배열의 길이를 구하면 끝!

 

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [N,S] = inputs.shift().split(' ').map(v => +v);
const nums = inputs.shift().split(' ').map(v => +v);

let temp = 0; // 수열의 길이를 넣어둘 값
let min = Number.MAX_SAFE_INTEGER; // 수열의 길이가 가장 짧은 값.

//왼쪽 포인터
for(let left = 0; left < N; left++){
  let sum = nums[left]; // 먼저 합계에 왼쪽 포인터 값을 넣어두고
  if(sum === S) { // 만약 값이 S가 된다면 min과 temp값이 1이 되고, 다음 값으로
    min = 1;
    temp = 1;
    continue;
  }

  let right = left+1; // 우측 포인터 설정

  while(right < N){ // 우측 포인터 움직이면서
    sum += nums[right]; // 합계 구하고
    if(sum >= S){ // 합계가 S이상인 순간
      temp = right - left + 1; // 배열의 길이를 임시 값에 넣어주고 반복문 종료.
      break;
    }

    right++; 
  }
  
  // 만약에 구해놨던 가장 짧은 배열의 길이보다 임시 값이 작아진다면 변경
  if(min > temp){
    min = temp;
  }
}

console.log(min)

 

3. 정리

- 반례 모음 사이트가 큰 도움이 되었다.

https://bingorithm.tistory.com/13

- 이제야 코딩 테스트 연습 방법을 좀 알 거 같다. 역시 쉽지 않다~