해당 포스팅은 백준 문제인 게으른 백곰 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였으며 슬라이딩 윈도우로 풀이하였다.
🐻 문제
문제
더운 여름날 동물원의 백곰 앨버트는 너무 더워서 꼼짝도 하기 싫다. 다행히도 사육사들이 앨버트의 더위를 식히기 위해 얼음이 담긴 양동이들을 가져다 주었다. 앨버트가 가장 적은 거리만 움직이고도 최대한 많은 얼음으로 더위를 식힐 수 있도록 도와주자.
우리 안은 1차원 배열로 생각하며, 총 N(1 ≤ N ≤ 100000)개의 얼음 양동이들이 xi(0 ≤ xi ≤ 1,000,000)좌표마다 놓여 있고 각 양동이 안에는 gi(1 ≤ gi ≤ 10,000)씩의 얼음이 들어 있다. 일단 앨버트가 자리를 잡으면 그로부터 좌우로 K(1 ≤ K ≤ 2,000,000) 만큼 떨어진 양동이까지 닿을 수 있다. 앨버트는 양동이가 놓여 있는 자리에도 자리잡을 수 있다. 모든 얼음 양동이의 위치는 다르다.
앨버트가 최적의 자리를 골랐을 때 얼음의 합을 구하시오. 즉, 얼음들의 합의 최댓값을 구해야 한다.
입력
첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다.
출력
앨버트가 택한 최적 위치로부터 K만큼 떨어진 거리 내에 있는 얼음들의 합(최댓값)을 출력한다.
🤔 풀이
1차원 배열인 우리 안에서 N개의 양동이가 주어진다.
백곰은 K만큼 이동할 수 있다.
백곰이 최적의 자리를 골랐을 때 얻을 수 있는 얼음의 합을 구하면 되는 문제이다.
백곰은 K만큼 이동할 수 있으므로 곰의 위치가 n이라 할 시 구간 [n-k, n+k] 안의 얼음들을 얻을 수 있다. 즉 백곰이 얻을 수 있는 얼음의 양은 2*k + 1 구간의 얼음의 합이다.
따라서 슬라이딩 윈도우를 이용해 2*k+1 크기의 윈도우를 만든 후 하나씩 넣고 빼주자.
로직
로직 설명은 해당 포스팅을 참고하였다.
슬라이딩 윈도우를 통해 예제 1을 표현하면 위의 사진과 같다. 편의상 idx를 0이 아닌 1부터 표기하였다.
예제 1에서 양동이들은 다음과 같은 양과 좌표를 지닌다.
양동이 1: [4 7]
양동이 2: [10 15]
양동이 3: [2 2]
양동이 4: [5 1]양동이 중 가장 좌표가 큰 값은 15(양동이 2)다.
좌표가 가장 큰 값 이후로 슬라이딩 윈도우를 진행하게 되면 값은 더 작아지게 된다.
따라서 슬라이딩 윈도우는 idx 1부터 15까지만 진행한다.
idx는 백곰이 자리잡을 수 있는 위치다. 즉 백곰은 idx 1부터 15까지 자리잡을 수 있다.
백곰이 idx 1일 때에는 k+1까지 얼음을 먹을 수 있다. 따라서 먼저 window를 [1, k+1]까지의 얼음의 합으로 초기화 한다.
그 다음 슬라이딩 윈도우를 통해 하나씩 넣고 빼주는 작업을 하면서 백곰이 먹을 수 있는 최대의 얼음을 구하자.
구현 방법
maxCoord: 양동이 중 가장 좌표가 큰 값. 예제 1의 경우 15(양동이 2)가 된다.
const maxCoord = board.reduce((prev, curr) => {
const coord = curr[1];
return Math.max(prev, coord);
}, 0);arr: 우리 크기를 maxCoord만큼 생성.
좌표가 가장 큰 값 이후로 슬라이딩 윈도우를 진행할수록 값은 더 작아지게 되기 때문에 maxCoord만큼 생성한다.
각 idx의 값은 각 좌표의 얼음의 양이다.
const arr = [...Array(maxCoord+1)].fill(0);
for (let row of board) {
const [ice, coord] = row;
arr[coord] = ice;
}window: 백곰이 idx 0의 위치일 때 k까지의 얼음을 먹을 수 있으므로 [0, k]까지의 얼음의 합으로 초기화.
let window = 0;
for (let i=0; i<k+1 && i<arr.length; i++) {
window += arr[i];
}-
maxIce: 백곰이 먹을 수 있는 최대 얼음양
슬라이딩 윈도우를 진행하면서 현재 윈도우의 값과 maxIce의 값 중 가장 큰 값으로 업데이트 -
for loop: 슬라이딩 윈도우
앞의 값(arr[lo])을 빼주고 뒤의 값(arr[hi])을 넣어준다.
이 때 앞의 값 혹은 뒤의 값이 undefined이면(배열의 범위에 벗어남) 0으로 세팅해준다.
let maxIce = 0;
for (let i=0; i<arr.length; i++) {
let lo = i-k-1;
let hi = i+k+1;
window = window - (arr[lo] ?? 0) + (arr[hi] ?? 0);
maxIce = Math.max(maxIce, window);
}🎨 전체 코드
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').map(s => s.split(" ")).slice(0,-1);
const NK = input.shift();
const [n,k] = NK.map(el => Number(el));
const board = input.map(s => s.map(el => Number(el)));
function solution(n,k,board) {
const maxCoord = board.reduce((prev, curr) => {
const coord = curr[1];
return Math.max(prev, coord);
}, 0);
const arr = [...Array(maxCoord+1)].fill(0);
for (let row of board) {
const [ice, coord] = row;
arr[coord] = ice;
}
let window = 0;
for (let i=0; i<k+1 && i<arr.length; i++) {
window += arr[i];
}
let maxIce = 0;
for (let i=0; i<arr.length; i++) {
let lo = i-k-1;
let hi = i+k+1;
window = window - (arr[lo] ?? 0) + (arr[hi] ?? 0);
maxIce = Math.max(maxIce, window);
}
return maxIce;
}
console.log(solution(n,k, board));(ref) 다른 사람 풀이
