문제 이해
길이가 같은 두 개의 숫자 배열 arr1과 arr2를 입력받는 JavaScript 함수를 작성해야 합니다.
함수의 목표는 첫 번째 배열 arr1의 요소들을 재배치(셔플)하여, arr2의 같은 위치에 있는 요소보다 큰 요소의 개수를 최대한 많이 만드는 것입니다. 재배치가 끝나면 그 배열을 반환하면 됩니다.
예를 들어, 함수에 다음과 같은 입력이 주어졌을 때를 살펴보겠습니다.
입력
const arr1 = [3, 5, 12, 19]; const arr2 = [2, 9, 3, 12];
출력
const output = [3, 12, 5, 19];
출력 설명
재배치 전의 arr1은 arr2보다 큰 요소가 3개뿐이었지만, 재배치 후에는 4개 모두 대응되는 요소보다 커졌습니다.
접근 방법: 탐욕(Greedy) 알고리즘
이 문제는 탐욕적 선택 전략으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
arr1을 내림차순으로 정렬해 가장 큰 값이 항상 맨 앞에 오도록 준비합니다.arr2의 인덱스들을 값 기준 내림차순으로 정렬합니다. 즉, 상대의 가장 강한 값부터 차례로 마주하게 됩니다.arr2의 각 위치를 순회하면서, 현재 가진 가장 큰 값(arr1[0])으로 해당 위치를 이길 수 있다면 그 값을 배치하고, 이길 수 없다면 가장 작은 값(arr1.pop())을 배치합니다.
이렇게 하면 승리 가능한 자리에는 승리에 필요한 최소한의 큰 값을 사용하고, 어차피 지게 되는 자리에는 가장 작은 값을 소모해 나머지 자리의 승률을 극대화할 수 있습니다.
구현 코드
const arr1 = [3, 5, 12, 19];
const arr2 = [2, 9, 3, 12];
const maximiseArray = (arr1 = [], arr2 = []) => {
arr1.sort((a, b) => b - a)
const indexes = arr2.map((v, index) => index).sort((a, b) => arr2[b] - arr2[a])
const res = []
for(let i = 0; i < indexes.length; i++) {
const index = indexes[i]
res[index] = arr1[0] > arr2[index] ? arr1.shift() : arr1.pop()
}
return res
}
console.log(maximiseArray(arr1, arr2));
실행 결과
[ 3, 12, 5, 19 ]
코드 상세 설명
arr1.sort((a, b) => b - a)는 arr1을 내림차순으로 정렬합니다. indexes는 arr2의 인덱스 배열을 arr2 값 기준 내림차순으로 정렬한 것으로, 상대의 큰 값부터 처리하기 위함입니다.
반복문 안에서는 삼항 연산자로 판단합니다. arr1[0](남은 값 중 최댓값)이 arr2[index]보다 크면 shift()로 최댓값을 꺼내 승리를 확정하고, 그렇지 않으면 pop()으로 최솟값을 꺼내 불필요한 손실을 최소화합니다. 결과 배열 res는 원래 인덱스 위치에 맞게 채워지므로, 반환 시 올바른 순서의 재배치 배열이 완성됩니다.
정렬에 O(n log n), 각 배치마다 shift()/pop() 연산이 들어가므로 전체 시간 복잡도는 O(n²)입니다. 배열이 매우 클 경우 큐(deque) 자료구조를 활용하면 O(n log n)까지 최적화할 수 있습니다.