sumZero 문제풀이
내 풀이
/*
문제
Write a function called sumZero,
which accepts a sorted array of integers.
The function should find the first pair where
the sum is 0. Return an array that includes both
values that sum to zero or undefined if a pair
does not exist
*/
function sumZero(arr) {
// 투 포인터 문제
let idx = 0;
let idx_ = arr.length - 1;
if (arr[idx] >= 0 || arr[idx_] <= 0){
return undefined;
}
while (arr[idx] < 0 && arr[idx_] > 0) {
while (arr[idx_] > 0 && Math.abs(arr[idx]) <= arr[idx_]) {
if (!(arr[idx] + arr[idx_])) {
return [arr[idx], arr[idx_]];
} else {
idx_--;
}
}
idx++;
}
return undefined;
}
console.log(sumZero([-3, -2, -1, 0, 1, 2, 3])); // [-3, 3]
console.log(sumZero([ -2, -1, 0, 3])); // undefined
console.log(sumZero([1,2,3])); // undefined
console.log(sumZero([ -2, -1, 1, 3])); // [-1, 1]
해설
- 더해서 0이 나와야됨.
- 가장 먼저 0이 된 값들을 리턴해야 되므로, 투 포인터 문제라고 생각이듦.
-> 투 포인터가 각각 0미만 0초과여야 한다.
-> 두 값의 합이 0이면 바로 리턴
-> 아니라면 idx 를 하나씩 줄임.
-> arr[idx]의 절대값이 arr[idx]의 절대값보다 크다면 idx를 +1에서 비교 - return 되지 않았다면, 합이 0을 만족하지 값들이 없으므로 undefined 리턴한다.
- 시간복잡도 O(N), 공간복잡도 O(1) -> 2중 while문처럼 보이지만 O(N)이다...
- 밑에 단순하게 이중 for문으로 도는 방법에 비해 시간복잡도를 줄일 수 있다.
// 시간 복잡도 O(N^2)
// 공간 복잡도 0(1)
function sumZero_(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === 0) {
return [arr[i], arr[j]];
}
}
}
return undefined;
}
console.log(sumZero_([-3, -2, -1, 0, 1, 2, 3])); // [-3, 3]
console.log(sumZero_([-2, -1, 0, 3])); // undefined
console.log(sumZero_([1, 2, 3])); // undefined
console.log(sumZero_([-2, -1, 1, 3])); // [-1, 1]
better practice
조건문을 너무 형편없이 쓴 것 같다.
while문을 굳이 2번 사용할 필요도 없었다.
밑에는 이상적인 답변이다.
- 간결하게 조건문을 사용하였다.
Author And Source
이 문제에 관하여(sumZero 문제풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@stthunderl/sumZero-문제풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)