백준/ Silver 3 문제 , 백준 Node.js 자바스크립트 10025 , 게으른 백곰

백준/ Silver 3 문제 , 백준 Node.js 자바스크립트 10025 , 게으른 백곰

 

 

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

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

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

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

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

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

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

문제 출처

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

 

 

 

풀이

 

 

 

https://velog.io/@dev-redo/%EB%B0%B1%EC%A4%80-10025%EB%B2%88-%EA%B2%8C%EC%9C%BC%EB%A5%B8-%EB%B0%B1%EA%B3%B0-NodeJS

[백준] 10025번 게으른 백곰 - NodeJS

 

*이 분 블로그 글을 참조 하였다.

 

우선, 제가 기존에 쓰던 input 받는 코드말고 프로그래머스 입력 받는것처럼 입력 받아 solution 함수로 처리하시던데 되게 좋아보였다. 보자마자 아? 왜 이생각을 못했지? 했네요 ㅋㅋㅋ

이렇게 받으면 한번 입력처리한 배열 재사용하기도 편하고 가독성도 좋은 것 같습니다.

 

백준보다 프로그래머스 입력 스타일을 더 선호하는 편이라 앞으로 백준 입력 처리는 이렇게 처리할려고 합니다. 좋은거 배웠네요.

 

---

 

이 문제는 메모리 초과가 계속 발생해서 애를 먹었다. 문제 로직 자체는 간단했는데,

 

처음 빈 배열을 초기화할때 나는 그냥 1,000,001 크기의 배열을 선언해주었다. 어차피 입력으로 1,00,000내의 값이 들어오니 다 처리 가능했다.

 

근데 자꾸 메모리 초과가 나서 MAX 값을 구해 +1 만큼 초기 배열을 유동적으로 줄여줬는데도 메모리초과.... 대체 어디서 문제지 한참 고민했다.

 

 

결과적으로 문제는 

 

 

이 부분이였다. 위에코드로 작성하면 메모리초과가 나고 아래 코드로 작성해야 통과한다.

 

 

 

내가 생각한 풀이는 물론 밑에 처럼 0 부터 다 체크해봐도 괜찮지만, 조금더 효율을 높이기 위해

 

"제일 작은 위치 값 - K" 부터 "제일 큰 값 - K" 값 까지의 범위 내에서만 체크해줄려고했다.

 

어차피 제일 작은 위치 값 - K -1 밑의 범위와 제일 큰값 -K+1 위의 범위들은 더이상 큰값이 안나오거나 해당사항이 없기때문.

 

ex)  K=2  , 좌표 5,7

 

0	1	2	3	4	5	6	7	8	9
X	X	X	O	O	O	X	X	X	X

 

 

위에서 3 기준 이미 1~5 번 범위를 체크해줬고

 

4기준 2~6번,

5기준 3~7번 범위만 체크해주면 된다

 

4~8 부터는 더이상 큰값이 나올 수 없다.

 

 

 

오히려 이렇게 범위를 줄어들게 만들어 체크했다고 생각했는데 메모리 초과가 나서 도무지 뭐가 문제인지 해결 못했다.

 

결국 기존에 하던대로 0~제일 큰 위치값까지로 체크해줬음.

 

 

 

 

 

 

 

 

 

 

정답

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));
const [N, K] = input.shift();
const coord = input.map((v) => v);

function solution(N, K, coord) {
  let MAX = 0;
  const arr = Array.from({ length: 1000001 }).fill(0);
  for (let [ice, place] of coord) {
    arr[place] = ice;
    MAX = MAX < place ? place : MAX;
  }

  let result = 0;
  for (let i = 0; i <= K; i++) result += arr[i] ?? 0;

  let answer = 0;
  for (let j = 0; j < MAX; j++) {
    let [left, right] = [j - K - 1, j + K + 1];
    result = result - (arr[left] ?? 0) + (arr[right] ?? 0);
    answer = Math.max(answer, result);
  }
  return answer;
}

console.log(solution(N, K, coord));