[Leetcode/TwoPointer] 977. Squares of a Sorted Array

해결 방법: 투 포인터(Two Pointers)

이 문제를 O(n log n) 정렬로 해결하는 것은 쉽지만, O(n) 시간 복잡도로 해결하려면 투 포인터(Two Pointers) 기법을 사용해야 한다.

핵심 아이디어

1. 음수가 포함된 정렬된 배열에서, 가장 큰 제곱값은 절댓값이 가장 큰 수에서 나온다.
2. 배열에서 절댓값이 가장 큰 숫자는 양쪽 끝에 위치해 있다. (가장 작은 수는 음수이고, 가장 큰 수는 양수이므로)
3. 왼쪽(left)과 오른쪽(right)에서 시작하는 두 개의 포인터를 사용하여 가장 큰 제곱값을 뒤에서부터 채운다.

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)  # 주어진 배열의 길이를 저장
        result = [0] * n  # 정렬된 제곱값을 저장할 결과 배열 (0으로 초기화)
        left = 0  # 왼쪽 포인터 (배열의 시작 위치)
        right = n - 1  # 오른쪽 포인터 (배열의 끝 위치)

        # 결과 배열을 뒤에서부터 채우기 위해 역순 반복문 실행
        for i in range(n - 1, -1, -1):  
            # 현재 left, right 위치의 값 중 절댓값이 큰 쪽을 선택
            if abs(nums[left]) < abs(nums[right]):  
                square = nums[right]  # 오른쪽 값이 더 크다면 선택
                right -= 1  # 오른쪽 포인터를 한 칸 왼쪽으로 이동
            else:
                square = nums[left]  # 왼쪽 값이 더 크거나 같다면 선택
                left += 1  # 왼쪽 포인터를 한 칸 오른쪽으로 이동

            result[i] = square * square  # 제곱값을 결과 배열의 현재 위치에 저장

        return result  # 정렬된 제곱 배열 반환

입력

• nums = [-4, -1, 0, 3, 10]

초기 상태

• nums: [-4, -1, 0, 3, 10]
• indices: 0 1 2 3 4 l
• eft → -4, right → 10
• result: [0, 0, 0, 0, 0]

반복 과정

i (반복)	nums[left]	nums[right]	선택된 값	result 업데이트	left or right 변경
4 (마지막)	-4	10	10	[0, 0, 0, 0, 100]	right -= 1
3	-4	3	-4	[0, 0, 0, 16, 100]	left += 1
2	-1	3	3	[0, 0, 9, 16, 100]	right -= 1
1	-1	0	-1	[0, 1, 9, 16, 100]	left += 1
0	0	0	0	[0, 1, 9, 16, 100]	left += 1

최종 출력

• [0, 1, 9, 16, 100]

시간 복잡도 분석

• 한 번의 for 루프를 통해 nums 배열을 순회하므로 O(n).
• 별도의 정렬 과정이 필요 없음.
• 추가 공간 사용 O(n) (result 배열을 생성).

요약

✅ 투 포인터(Two Pointers) 활용: 절댓값이 가장 큰 요소를 양쪽 끝에서 비교하면서 큰 값을 result 배열에 뒤에서부터 채운다.
✅ O(n) 시간 복잡도: 한 번의 for 루프만 사용하여 최적화된 성능을 제공한다.
✅ O(n) 공간 복잡도: 출력 배열을 추가로 사용하지만, 별도의 정렬이 필요하지 않아 효율적이다.