누적합 문제 (GD5 개똥벌레)

문제

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

알고리즘 분류: 누적합

풀이

입력값
6 7
1
5
3
3
5
1

입력값이 위와 같이 주어졌을 때, 각 높이마다 장애물의 수를 구하면 된다. 즉, 위 입력값에서 [3, 2, 3, 2, 3, 2, 3] 을 도출하고 Math.min() 을 통해 최소값과 최소값의 개수를 구하면 된다.

Today I Learned

처음 코드

처음 구현할 때 [3, 2, 3, 2, 3, 2, 3] 을 도출하는 과정에서 시간 초과가 발생했다.

입력값으로 받은 석순과 종유석의 높이값만으로 결과를 도출했기 때문에 누적합을 구할 때 2중 for 문을 사용하였다.

/* 처음 작성한 코드 */

const sucksun = array.filter(
  (v, index) => index % 2 === 0
); // sucksun: [ 1, 3, 5]
const jongyusuck = array.filter(
  (v, index) => index % 2 !== 0
); // jongyusuck: [5, 3, 1]

const arr = new Array(H).fill(0);
for (let i = 0; i < sucksun.length; i++) {
  for (let j = 0; j < sucksun[i]; j++) arr[j]++;
} 
// arr: [ 3, 2, 2, 1, 1, 0, 0 ]


for (let i = 0; i < jongyusuck.length; i++) {
  for (let j = 0; j < jongyusuck[i]; j++) arr[arr.length - 1 - j]++;
} 
// arr: [ 3, 2, 3, 2, 3, 2, 3 ]

수정 코드

1. 석순과 종유석의 높이값에 대응되는 인덱스를 저장한다.
2. 석순은 배열의 뒤에서부터 누적합을 계산하고 종유석은 배열의 앞에서부터 누적합을 계산한다.

/* 수정한 코드 */
let sucksun = new Array(H + 1).fill(0);
let jongyusuck = new Array(H + 1).fill(0);
array.filter((v, index) =>
  index % 2 === 0 ? jongyusuck[H - v + 1]++ : sucksun[v]++
);

// sucksun: [ 0, 1, 0, 1, 0, 1, 0, 0 ]
// jongyusuck: [ 0, 0, 0, 1, 0, 1, 0, 1 ]

for (let i = 1; i <= H; i++) {
  sucksun[H - i] += sucksun[H - i + 1];
  jongyusuck[i] += jongyusuck[i - 1];
}

// sucksun: [ 3, 3, 2, 2, 1, 1, 0, 0 ]
// jongyusuck: [ 0, 0, 0, 1, 1, 2, 2, 3 ]

let newArr = [];
for (let i = 1; i <= H; i++) {
  newArr[i - 1] = sucksun[i] + jongyusuck[i];
}

// newArr: [ 3, 2, 3, 2, 3, 2, 3 ]