24.07.05 23:53 작성
·
96
0
const solve = (a,b) => {
let left = 0, right = 0
const n = a.length + b.length;
const answer = [];
for (let i = 0; i < n; i++) {
if (a[left] < b[right]) {
answer.push(a[left]);
left ++
} else {
answer.push(b[right])
right ++
}
}
console.log(answer)
}
const a = [1,3,5];
const b = [2,3,6,7,9]
console.log(solve(a,b));
반례가 있을까요?
답변 2
0
2024. 07. 08. 06:41
안녕하세요^^
만약 아래와 같이 코드가 된다면 두 배열을 합치지 못합니다.
const solve = (a,b) => {
let left = 0, right = 0
const n = a.length + b.length;
const answer = [];
for (let i = 0; i < n; i++) {
if (a[left] > b[right]) {
answer.push(b[right]);
right ++
} else {
answer.push(a[left])
left ++
}
}
console.log(answer)
}
const a = [1,3,5];
const b = [2,3,6,7,9]
console.log(solve(a,b));
결과가
[1, 2, 3, 3, 5, undefined, undefined, undefined] 나올겁니다.
왜냐하면 a 배열의 값이 다 들어가고 나면 a[left] 값은 undefined 이 되고,
undefined과 숫자의 크기 비교는 항상 false 결과를 가져옵니다.
0
안녕하세요, 인프런 AI 인턴입니다.
hollis9797님, 제공하신 코드를 확인해보니 반례가 있습니다.
문제는 a
배열과 b
배열이 각각 완전히 순회되지 않았을 때 발생합니다. 이는 두 배열 중 하나가 끝에 도달했을 때, 다른 배열의 남은 요소들이 답에 추가되지 않기 때문입니다.
예를 들어, a
배열의 모든 요소가 answer
배열에 추가되었고 b
배열에 요소가 남아있는 경우, 남은 b
배열의 요소들이 답에 포함되지 않습니다. 이 상황은 b
배열의 모든 요소가 추가되었고 a
배열에 요소가 남아있는 경우에도 동일하게 적용됩니다.
이 문제를 수정하기 위해서는, 두 배열 중 하나라도 완전히 순회된 후에 남은 배열의 요소들을 answer
배열에 추가하는 로직이 필요합니다.
아래 수정된 코드는 이러한 케이스를 처리합니다:
const solve = (a, b) => {
let left = 0, right = 0;
const n = a.length, m = b.length;
const answer = [];
while (left < n && right < m) {
if (a[left] < b[right]) {
answer.push(a[left++]);
} else {
answer.push(b[right++])
}
}
// 남은 요소들을 처리
while (left < n) answer.push(a[left++]);
while (right < m) answer.push(b[right++]);
console.log(answer);
return answer;
}
const a = [1,3,5];
const b = [2,3,6,7,9]
console.log(solve(a, b));
이 코드는 a
와 b
배열의 모든 요소를 올바르게 순회하고, 어느 한 배열을 완전히 순회한 후 남은 배열의 요소들을 결과에 추가합니다.