[백준 2003] 수들의 합 2 (Javascript)

👩🏻‍💻문제링크

[백준 2003] 수들의 합 2 (Javascript)

✍️Idea Sketch

2021-07-19

1. 문제 이해

• 연속한 수들의 합이 M을 넘는 경우의 수 구하기

2. 백준 javascript 입력받기

const fs = require('fs');
const stdin = (process.platform === 'linux'
  ? fs.readFileSync('/dev/stdin').toString()
  : `10 5
1 2 3 4 2 5 3 1 1 2`
).split('\n');
 
let [N, M] = stdin[0].split(' ').map(Number);
let input = stdin[1].split(' ').map(Number);

3. 로직

• left, right 슬라이딩 윈도우
• sum이 M보다 작으면 sum += input[++right];
• sum이 M보다 크면 sum -= input[left++];
• sum이 M과 같으면 cnt++, sum += input[++right];
• 언제까지 반복하나요 : left < arr.length && right < arr.length
• left right sum 초기값 : 0, 1, input[left] + input[right]

✍️소스코드

2021-07-19 실패

반례

4 2  // N, M
2 3 1 1

문제상황 : 첫번째 원소 2가 M과 일치하는데도 경우의 수에 포함X
원인 : left, right, sum 초기값이 잘못됨

const fs = require('fs');
const stdin = (process.platform === 'linux'
  ? fs.readFileSync('/dev/stdin').toString()
  : `4 2
1 3 1 1`
).split('\n');
 
let [N, M] = stdin[0].split(' ').map(Number);
let input = stdin[1].split(' ').map(Number);
 
let result = 0;
let left = 0, right = 1;
let sum = input[left] + input[right];
 
while(left < N && right < N) {
  if (sum === M) {
    result++;
    sum += input[++right];
  }
  else if (sum < M) sum += input[++right];
  else if (sum > M) sum -= input[left++];
}
 
console.log(result);

2021-07-19 성공, 136ms

const fs = require('fs');
const stdin = (process.platform === 'linux'
  ? fs.readFileSync('/dev/stdin').toString()
  : `4 2
2 3 1 1`
).split('\n');
 
let [N, M] = stdin[0].split(' ').map(Number);
let input = stdin[1].split(' ').map(Number);
 
let result = 0;
let left = 0, right = 0;
let sum = input[left];
 
while(left < N && right < N) {
  if (sum === M) {
    result++;
    sum += input[++right];
  }
  else if (sum < M) sum += input[++right];
  else if (sum > M) sum -= input[left++];
}
 
console.log(result);