JavaScript로 오름차순 정렬된 숫자 제곱 배열 구하기

문제 소개

오름차순으로 정렬된 정수 배열 arr을 입력받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열의 각 숫자를 제곱한 값들을 담은 배열을 반환하며, 반환되는 배열 역시 오름차순으로 정렬되어 있어야 합니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

const arr = [-2, -1, 1, 3, 6, 8];

그렇다면 기대되는 출력은 다음과 같습니다.

const output = [1, 1, 4, 9, 36, 64];

접근 방법: 투 포인터(Two Pointer) 기법

배열이 이미 정렬되어 있다는 점을 활용하면, 모든 요소를 제곱한 뒤 다시 정렬하는 것보다 훨씬 효율적으로 문제를 해결할 수 있습니다. 핵심 아이디어는 투 포인터 기법입니다.

배열에 음수가 포함된 경우, 음수라도 제곱하면 큰 양수가 될 수 있습니다. 따라서 배열의 양쪽 끝에 포인터를 두고, 두 포인터가 가리키는 값의 제곱을 서로 비교합니다. 더 큰 제곱 값을 결과 배열에 추가하고 해당 포인터를 안쪽으로 한 칸 이동시킵니다. 이 과정을 반복한 뒤, 내림차순으로 채워진 결과 배열을 뒤집으면 최종적으로 오름차순 배열을 얻을 수 있습니다.

예제 코드

위 접근 방식을 구현한 코드는 다음과 같습니다.

const arr = [-2, -1, 1, 3, 6, 8];
const findSquares = (arr = []) => {
    const res = []
    let left = 0
    let right = arr.length - 1
    while (left <= right) {
        const leftSquare = arr[left] * arr[left]
        const rightSquare = arr[right] * arr[right]
        if (leftSquare < rightSquare) {
            res.push(rightSquare)
            right -= 1
        } else {
            res.push(leftSquare)
            left += 1
        }
    }
    return res.reverse();
};
console.log(findSquares(arr));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[ 1, 1, 4, 9, 36, 64 ]

복잡도 분석

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 결과를 저장할 배열이 필요하므로 공간 복잡도 역시 O(n)입니다. 반면 모든 요소를 제곱한 후 sort()를 사용하는 방식은 O(n log n)의 시간이 걸리므로, 입력 배열이 이미 정렬되어 있는 상황에서는 투 포인터 기법이 훨씬 유리합니다.