문제 개요
정렬된 숫자 리스트가 주어졌을 때, 각 요소를 제곱한 결과를 다시 정렬된 순서로 반환하는 문제입니다. 입력 리스트에는 음수와 0도 포함될 수 있다는 점이 특징입니다.
예를 들어, 입력이 [-12,-6,-5,-2,0,1,2,4,8,9,10,15,18,20,35,38,69]라면 출력은 다음과 같습니다.
[0, 1, 4, 4, 16, 25, 36, 64, 81, 100, 144, 225, 324, 400, 1225, 1444, 4761]
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 새로운 리스트 L을 생성합니다.
- nums의 각 요소 e에 대해 e²(제곱 값)를 L에 삽입합니다.
- L을 오름차순으로 정렬하여 반환합니다.
파이썬에서는 제너레이터 표현식과 내장 함수 sorted()를 함께 사용하면 위 과정을 한 줄로 매우 간결하게 처리할 수 있습니다.
구현 예제
class Solution:
def solve(self, nums):
return sorted(x * x for x in nums)
ob = Solution()
nums = [-12, -6, -5, -2, 0, 1, 2, 4, 8, 9, 10, 15, 18, 20, 35, 38, 69]
print(ob.solve(nums))
입력
[-12,-6,-5,-2,0,1,2,4,8,9,10,15,18,20,35,38,69]
출력
[0, 1, 4, 4, 16, 25, 36, 64, 81, 100, 144, 225, 324, 400, 1225, 1444, 4761]
시간 복잡도와 최적화 팁
위 방법의 시간 복잡도는 O(n log n)이며, n은 리스트의 길이입니다. 공간 복잡도는 O(n)입니다.
만약 입력 리스트가 이미 정렬되어 있다는 조건을 활용하면, 투 포인터(two-pointer) 기법으로 O(n) 시간에 해결할 수 있습니다. 리스트의 양 끝에서 시작해 절댓값이 큰 쪽의 제곱 값을 결과 리스트의 뒤부터 차례로 채워 나가는 방식으로, 음수가 포함된 정렬 리스트에서 특히 효과적입니다.