Squares of a Sorted Array — 절댓값 기준 투 포인터로 `O(n)` 정렬 유지하기

제곱한 뒤에도 정렬된 배열로 만들기, 어떤 문제인가요?

LeetCode 977번 문제는 이렇게 주어집니다.

오름차순으로 정렬된 정수 배열 nums가 주어집니다. 각 원소를 제곱한 뒤, 다시 오름차순으로 정렬된 배열을 반환하세요.

예시는 이렇습니다.

• nums = [-4, -1, 0, 3, 10] → [0, 1, 9, 16, 100]
• nums = [-7, -3, 2, 3, 11] → [4, 9, 9, 49, 121]

제약은 다음과 같습니다.

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums는 오름차순으로 정렬되어 있음

문제의 follow-up은 제곱 후 정렬하는 단순한 방법 말고, O(n)으로 풀 수 있는가입니다.

핵심은 원본 배열은 정렬되어 있지만, 제곱하면 음수 쪽 큰 절댓값이 앞쪽 큰 양수로 바뀌어 순서가 깨진다는 점입니다. 이 글에서는 제곱 후 정렬하는 O(n log n) 풀이부터, 양끝 절댓값을 비교해 결과를 뒤에서 채우는 투 포인터 O(n) 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

왜 원래 정렬이 제곱 후에는 깨지나요?

입력 nums = [-4, -1, 0, 3, 10]는 이미 정렬되어 있습니다.

-4 < -1 < 0 < 3 < 10

그런데 제곱하면:

16, 1, 0, 9, 100

이 됩니다. 여기서 -4는 가장 앞에 있었지만, 제곱 후 16이 되어 꽤 큰 값이 됩니다. 즉 원래 정렬 순서는 값 기준이었고, 제곱 후에는 사실상 절댓값 기준 크기가 더 중요해집니다.

그래서 이 문제는 단순한 정렬 문제가 아니라:

가장 큰 제곱값은 어디에서 나오는가?

를 먼저 봐야 합니다. 답은 배열 양끝입니다.

• 가장 왼쪽: 큰 절댓값의 음수일 수 있음
• 가장 오른쪽: 큰 양수일 수 있음

즉 가장 큰 제곱값은 항상 양끝 중 하나에서 나옵니다.

Phase 1. 제곱한 뒤 다시 정렬하기

가장 먼저 떠올릴 수 있는 방법은 모든 값을 제곱한 뒤 정렬하는 것입니다.

fun sortedSquares(nums: IntArray): IntArray {
    val result = IntArray(nums.size)

    for (i in nums.indices) {
        result[i] = nums[i] * nums[i]
    }

    result.sort()
    return result
}

nums = [-4, -1, 0, 3, 10]라면:

• 제곱 후: [16, 1, 0, 9, 100]
• 정렬 후: [0, 1, 9, 16, 100]

이 풀이는 구현이 짧고 틀릴 여지가 적습니다. 다만 정렬에 O(n log n)이 필요합니다. 문제의 follow-up이 O(n)을 요구하므로, 여기서 한 단계 더 가야 합니다.

Phase 2. 투 포인터 — 가장 큰 제곱부터 뒤에 채우기

가장 큰 제곱값이 양끝 중 하나에서 나온다면, 결과 배열의 맨 뒤부터 채우는 것이 자연스럽습니다.

• left = 0
• right = nums.lastIndex
• write = nums.lastIndex
• abs(nums[left])와 abs(nums[right])를 비교
• 더 큰 쪽의 제곱을 result[write]에 넣고 포인터 이동

코드는 이렇게 됩니다.

fun sortedSquares(nums: IntArray): IntArray {
    val result = IntArray(nums.size)
    var left = 0
    var right = nums.lastIndex
    var write = nums.lastIndex

    while (left <= right) {
        val leftSquare = nums[left] * nums[left]
        val rightSquare = nums[right] * nums[right]

        if (leftSquare > rightSquare) {
            result[write] = leftSquare
            left++
        } else {
            result[write] = rightSquare
            right--
        }

        write--
    }

    return result
}

nums = [-4, -1, 0, 3, 10]를 따라가 봅시다.

left=0 (-4), right=4 (10), write=4
16 vs 100 -> 100이 더 큼 -> result[4] = 100, right--

left=0 (-4), right=3 (3), write=3
16 vs 9 -> 16이 더 큼 -> result[3] = 16, left++

left=1 (-1), right=3 (3), write=2
1 vs 9 -> 9가 더 큼 -> result[2] = 9, right--

left=1 (-1), right=2 (0), write=1
1 vs 0 -> 1이 더 큼 -> result[1] = 1, left++

left=2 (0), right=2 (0), write=0
0 vs 0 -> result[0] = 0

최종 결과는:

[0, 1, 9, 16, 100]

입니다.

시간 복잡도는 O(n)입니다. 각 포인터가 한 방향으로만 움직이기 때문입니다. 추가 공간은 결과 배열 때문에 O(n)입니다.

왜 뒤에서부터 채워야 하나요?

매 단계에서 확실히 알 수 있는 것은 남아 있는 값들 중 가장 큰 제곱값뿐입니다.

예를 들어:

nums = [-7, -3, 2, 3, 11]

남아 있는 값들의 제곱 중 최댓값은 항상 양끝 -7, 11 중 하나에서 나옵니다. 이 값은 결과 배열의 맨 앞이 아니라 맨 뒤로 가야 합니다.

따라서:

• 큰 값부터 확정할 수 있음
• 큰 값은 결과 뒤쪽에 들어가야 함

이 두 조건이 맞물려서 결과 배열을 뒤에서부터 채우게 됩니다.

만약 앞에서부터 채우려 하면, 지금 구한 값이 최솟값인지 최댓값인지 확정되지 않아서 곤란합니다. 반면 뒤쪽은 항상 "현재 남은 것 중 최댓값 자리"라서 안전하게 채울 수 있습니다.

절댓값 비교와 제곱 비교는 왜 같은가요?

우리는 사실:

abs(nums[left]) 와 abs(nums[right]) 중 누가 더 큰가?

를 비교하고 싶은 것입니다. 코드에서는 이렇게 쓰지 않고:

val leftSquare = nums[left] * nums[left]
val rightSquare = nums[right] * nums[right]

를 비교했습니다.

이유는 두 값이 음수가 아니기 때문입니다. 절댓값이 더 큰 쪽은 제곱값도 더 큽니다.

예를 들어:

• abs(-4) = 4, abs(3) = 3
• (-4)^2 = 16, 3^2 = 9

따라서 절댓값을 비교해도 되고, 제곱값을 바로 비교해도 됩니다. 현재 범위에서는 nums[i]가 10^4 이하라 제곱해도 10^8 수준이므로 Kotlin Int 범위를 넘지 않습니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
[0]	[0]	원소 하나
[1]	[1]	양수 하나
[-1]	[1]	음수 하나
[-3, -2, -1]	[1, 4, 9]	전부 음수
[0, 2, 3]	[0, 4, 9]	전부 0 이상
[-4, -1, 0, 3, 10]	[0, 1, 9, 16, 100]	기본 예시

특히 전부 음수인 경우가 중요합니다. 원래 배열은 정렬되어 있어도 제곱하면 완전히 뒤집힌 형태가 되기 때문입니다.

두 풀이를 다시 비교

풀이	시간	공간	특징
제곱 후 정렬	O(n log n)	O(n)	가장 직관적이지만 follow-up을 만족하지 못함
투 포인터로 뒤에서 채우기	O(n)	O(n)	양끝 절댓값 비교로 정렬을 유지한 채 결과 구성

마무리

1. 정렬된 배열도 제곱하면 순서가 깨질 수 있습니다 — 큰 절댓값의 음수가 큰 양수로 바뀌기 때문입니다
2. 가장 큰 제곱값은 항상 양끝 중 하나에서 나옵니다 — 왼쪽의 큰 음수 절댓값과 오른쪽의 큰 양수를 비교하면 됩니다
3. 그래서 결과 배열을 뒤에서부터 채우는 투 포인터가 성립합니다 — 매 단계에서 가장 큰 값부터 확정할 수 있습니다
4. 시간 복잡도는 O(n)입니다 — 정렬 없이 한 번의 스캔으로 끝납니다
5. 이 문제의 핵심은 "정렬된 값"이 아니라 "정렬된 절댓값의 양끝 후보"를 이용하는 관점 전환입니다 — follow-up의 핵심도 여기에 있습니다