[JS] 백준 1806번 : 부분합 - 누적 합, 투 포인터, 효울성

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

1806번: 부분합

 

 

효율성 문제이다.

투포인터를 이용해서 조건에 맞는 수열의 부분합을 찾는 것이다.

 

📋풀이방법

1. lt와 rt를 사용해야하므로 선언한다.

 - lt는 0으로 초기화해주고, rt는 for문을 이용해 N까지 증가하면서 순회한다.

2. 0 ~ N까지 순회하면서 result 변수 안에 주어진 수열 arr에서 arr[rt]를 하나씩 누적해본다.

3. 만약 result가 S보다 크거나 같다면 while문으로 들어간다

 -while문에서는 result가 S보다 작아질때까지 반복한다.

 -먼저 answer에 현재 누적했던 수열의 길이를 rt-lt+1로 기록한다 -> 누적했던 수열의 길이

 - 그리고 result에서 arr[lt]값을 빼준다 -> lt는 0에서부터 시작한다.

 - lt는 ++로 증가시켜준다.

 - result에서 arr[lt] 안의 값을 빼줬는데도 S보다 크거나 같다면 정답이므로 한번 더 기록해줘야한다.

4. answer은 Math.min()을 통해 가장 최단 길이를 저장한다.

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

let [N, S] = input[0].split(" ").map(Number);
let arr = input[1].split(" ").map(Number);

let lt = 0;
let result = 0;
let answer = N;
let check = false;
for (let rt = 0; rt < N; rt++) {
  result += arr[rt];
  while (result >= S) {
    check = true;
    answer = Math.min(answer, rt - lt + 1);
    result -= arr[lt++];
    if (result >= S) answer = Math.min(answer, rt - lt + 1);
  }
}
console.log(check ? answer : 0);

 

 

💢어려웠던 점

1. 문제에서 "그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다." 를 체크하지 않아 오답이 생겼다.

-처음에 이 조건을 안해줘서 틀렸고, 아래처럼 코드를 작성했다,

-하지만 또 틀리게 되었다.

console.log(answer == N ? 0 : answer);

-여기서 정답이 N이 될 수도 있으므로 이 코드는 오답이다. 아래처럼 바꿔줘야했다.

let check=false;

...

  while (result >= S) {
    check = true;
    
    ...
    
  }
}

console.log(check ? answer : 0);

-만약 S보다 이상일 때의 수열을 찾는다면 check를 해줘서 정답을 출력할 때 사용했다.