문제 개요
오름차순으로 정렬된 숫자 리스트 nums가 주어졌을 때, 각 요소를 제곱한 후 그 결과를 다시 정렬된 순서로 반환하는 것이 이번 문제의 목표입니다.
예를 들어 입력이 nums = [-8, -3, 0, 5, 6]이라면, 각 요소를 제곱한 값은 [64, 9, 0, 25, 36]이 되고, 이를 정렬하면 최종 출력은 [0, 9, 25, 36, 64]가 됩니다.
접근 방법: 투 포인터(Two Pointer) 기법
모든 요소를 제곱한 뒤 다시 정렬하면 O(n log n)의 시간이 필요하지만, 입력 리스트가 이미 정렬되어 있다는 특성을 활용하면 투 포인터 기법으로 O(n) 시간에 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 음수는 제곱하면 양수가 되므로, 가장 큰 제곱값은 항상 리스트의 양 끝(가장 작은 음수 또는 가장 큰 양수)에서 발생합니다. 따라서 왼쪽 끝을 가리키는 포인터 l과 오른쪽 끝을 가리키는 포인터 r을 두고, 절댓값이 더 큰 쪽의 제곱값을 결과 배열의 뒤에서부터 차례대로 채워 나가면 됩니다.
알고리즘 단계
- n := nums의 길이
- l := 0, r := n - 1
- index := n - 1
- res := nums와 같은 크기의 0으로 초기화된 리스트 생성
- index >= 0인 동안 반복:
- |nums[l]| > |nums[r]|이면 res[index] := nums[l] * nums[l] 후 l을 1 증가
- 그렇지 않으면 res[index] := nums[r] * nums[r] 후 r을 1 감소
- index를 1 감소
- res 반환
구현 예제
아래 구현 예제를 통해 동작 방식을 더 자세히 살펴보겠습니다.
def solve(nums):
n = len(nums)
l = 0
r = n - 1
index = n - 1
res = [0 for i in range(len(nums))]
while index >= 0:
if abs(nums[l]) > abs(nums[r]):
res[index] = nums[l] * nums[l]
l += 1
else:
res[index] = nums[r] * nums[r]
r -= 1
index -= 1
return res
nums = [-8, -3, 0, 5, 6]
print(solve(nums))입력
[-8, -3, 0, 5, 6]
출력
[0, 9, 25, 36, 64]
복잡도 분석
시간 복잡도: O(n) — 리스트의 각 요소를 정확히 한 번씩만 처리합니다.
공간 복잡도: O(n) — 결과를 저장할 크기 n의 추가 리스트가 필요합니다.
이처럼 이미 정렬된 데이터의 구조적 특성을 활용하면 불필요한 재정렬 없이 선형 시간 안에 문제를 해결할 수 있습니다. 투 포인터 기법은 정렬된 배열 문제에서 매우 자주 활용되는 패턴이므로 꼭 익혀두시길 권장합니다.