백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 1806 부분합

백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 1806 부분합 

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

문제 출처 🏠

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

1806번: 부분합

 

 

문제풀이 소감 🧑‍💻

단순하게 생각해서 접근했는데 풀리는 문제였다.

 

시간복잡도에서 과연 통과할 것인가했지만 무난하게 통과하였음.

 

 

 

요구사항 📋

• 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다.
• 둘째 줄에는 수열이 주어진다.
• 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

 

• 첫째 줄에 구하고자 하는 최소의 길이를 출력한다.
• 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

해결 전략 📝

 

아이디어는 간단하다.

 

시작점을 0 ~ N-1 번인덱스로 각각 잡아보고 다 탐색해본다.

 

0 ~ N-1 

1 ~ N-1

2 ~ N-1

.

.

.

N-2 ~ N-1

 

의 구간을 각각 잡고 S보다 커지는 순간의 길이를 각 시작점 인덱스에 맞게 저장해둔다.

 

그리고 모든 탐색을 마친 뒤 가장 짧은 길이를 출력하면 된다.

 

 

만약 0 ~ N-1  구간에서 모든 숫자를 다 더하였음에도 S보다 작다면 바로 0을 출력하고 종료시켜버린다.

 

 0 ~ N-1  구간의 모든 숫자를 다 더했는데 S보다 작다면 다른 구간들은 더 살펴볼 필요도 없기 때문이다.

 

 

 

 

 

 

정답 💯

 

 

const { exit } = require("process");
const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [input_NS, input_nums] = input.map((v) => v.split(" ").map(Number));

function solution(N, S, nums) {
  const len = Array.from({ length: N }).fill(0);
  let MIN = Infinity;
  nums.forEach((_, idx) => {
    let store = 0;
    let cnt = 0;
    for (let i = idx; i < N; i++) {
      store += nums[i];
      cnt += 1;
      if (store >= S) {
        len[idx] = cnt;
        if (MIN > cnt) MIN = cnt;
        break;
      }
    }
    if (idx === 0 && len[0] === 0) {
      console.log(0);
      exit(0);
    }
  });
  return MIN;
}

console.log(solution(input_NS[0], input_NS[1], input_nums));