https://www.acmicpc.net/problem/11659
//test.txt
5 3
5 4 3 2 1
1 3
2 4
5 5
sol1 - 메모리 초과
let input = require('fs').readFileSync('test.txt').toString().trim().split('\n');
let nums = input.map(v => v.split(' ').map(Number));
function solution(nums) {
let answer = '';
for(let i = 2;i<nums[0][1]+2;i++) {
let [start,end] =nums[i];
let arr = nums[1].slice(start-1,end).reduce((acc,cur) => acc+cur,0);
answer += `${arr}\n`
}
return answer
};
console.log(solution(nums));
// 12
// 9
// 1
입력받는데 제법 고생해서 테스트 케이스 출력되는 것 보고 세상 뿌듯했는데 초과가 떴다... 테스트에 들어가는 숫자는 10만 정도로 높은 편은 아니었는데 로직이 문제인 듯하다.
1.
let nums = input.map(v => v.split(' ').map(Number));
console.log(nums)
// [ [ 5, 3 ],
// [ 5, 4, 3, 2, 1 ],
// [ 1, 3 ],
// [ 2, 4 ],
// [ 5, 5 ] ]
우선 각 요소를 숫자로 바꾸고 배열에 담기 위해서 map 메서드를 돌렸다.
2.
function solution(nums) {
let answer = '';
for(let i = 2;i<nums[0][1]+2;i++) {
let [start,end] =nums[i];
let arr = nums[1].slice(start-1,end).reduce((acc,cur) => acc+cur,0);
answer += `${arr}\n`
}
return answer
};
답을 받기 위한 빈 배열을 만들고, 문제 출력이 세로로 되어있어서 백틱과 줄 바꿈을 이용해 담아 주었다.
nums 배열의 처음과 두 번째 행은 문제를 입력받기 위한 배열이므로 for문을 index 2부터 돌아준다. 선택된 배열을 start와 end로 받고 arr 배열에 start와 end 사이 값만 잘라서 저장했다. arr 배열에 reduce 메서드를 이용해 값만 받고, answer에 넣어 출력했다.
이 방법은 테스트 케이스가 들어올 때마다 매번 배열을 start와 end가 나올 때까지 돌아야 하는 게 메모리 초과의 원인이 아닌가 생각한다.
sol2
let input = require('fs').readFileSync('test.txt').toString().trim().split('\n');
let nums = input.map(v => v.split(' ').map(Number));
let array = Array.from({length : nums[1].length+1}, ()=>0);
let answer = [];
nums[1].forEach((el,i) => {
array[i+1] = array[i] + el;
});
for(let i=2;i<nums[0][1]+2;i++) {
let [start,end] = nums[i];
answer.push(array[end] -array[start-1])
};
console.log(answer.join('\n'));
// 12
// 9
// 1
빈 배열에 누적합을 저장하고 있다가 start로 받은 입력만큼 빼주는 방식으로 출력한다. 배열의 합을 미리 구해놓고 start와 end는 배열합에서 빼기만 하면 되기 때문에 sol1 보다 훨씬 간단했다.
1.
let array = Array.from({length : nums[1].length+1}, ()=>0);
let answer = [];
nums[1].forEach((el,i) => {
array[i+1] = array[i] + el;
});
console.log(array);
//[ 0, 5, 9, 12, 14, 15 ]
빈 배열 array를 만들고 누적합을 담아두었다. for 문에서 array [start-1] 값이 들어가야 하기 때문에 배열 길이를 한 칸 늘려 index 0 이 0을 갖고 있어야 한다.
2.
for(let i=2;i<nums[0][1]+2;i++) {
let [start,end] = nums[i];
answer.push(array[end] -array[start-1])
};
// 12 - 0 = 12
// 14 - 5 = 9
// 15-14 = 1
누적합 배열의 end에서 start-1 만큼 빼주면 구간합이 출력된다.
구간에 대한 답이 필요할 때 그 구간을 잘라 쓰는 것보다 요구하는 조건의 배열을 만들어두고 거기서 구간만큼 빼서 쓰는 게 훨씬 효율적인 것 같다.
'Study > Algorithm' 카테고리의 다른 글
[BEAKJOON / node.js] 1920 수 찾기 (2) | 2022.06.12 |
---|---|
[BEAKJOON / node.js] 10816 숫자 카드 2 (0) | 2022.06.11 |
[BEAKJOON / node.js] 1439 뒤집기 (0) | 2022.06.08 |
[BEAKJOON / node.js] 2775 부녀회장이 될테야 (0) | 2022.06.07 |
<programmers / JavaScript> 신고 결과 받기 (0) | 2022.06.03 |