1. Problem Description

link

Summary
주어진 배열의 각 요소를 제곱하고 오름차순으로 정렬한다.
example

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Constraints

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.

2. Approach to the Problem

• 주어진 배열을 for문 으로 순회합니다.
• 각 요소를 제곱합니다.
• 제곱한 요소를 배열에 추가합니다.
• 각 제곱한 요소를 정렬 후 return 합니다.

3. Code and Explanation

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        sorted_nums = []

        for i in nums:
            num = i*i
            sorted_nums.append(num)

        return sorted(sorted_nums)

• sorted_nums : 제곱한 요소를 저장할 배열
• for문을 통해 nums의 요소를 순회하면서 제곱합니다.
• 제곱한 요소는 append()를 통해 배열에 추가합니다.
• 모든 요소의 순회가 끝나면 마지막으로 sorted() 를 사용하여 정렬합니다.

4. Time and Space Complexity Analysis

빅오 표기법(Big-O Notation)에서는 가장 큰 복잡도를 남기고 작은 것은 무시합니다.

Time Complexity

• O(N log N)
• sorted() 함수는 Timsort 알고리즘을 사용하며, 평균 및 최악의 경우 O(N log N)

Space Complexity

• O(N)
• sorted()는 새로운 정렬된 리스트를 생성하기 때문에 추가적으로 O(N) 공간이 필요.

탐색에서는 O(log N)이 유리하지만, 전체 데이터를 다 봐야 하면 O(N)이 필요할 수있다.

5. Alternative Approaches

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted([x * x for x in nums])

• 리스트 컴프리헨션 활용

6. Improvements

sorted() vs .sort() 차이점

sorted()

• 새로운 정렬된 리스트 반환
• 원본 리스트 변경되지 않음
• 리스트, 튜플 등 반복 가능한 모든 데이터 구조에 사용가능
• sorted(lst)

.sort()

• 기존 리스트를 직접 정렬
• None (리스트 자체를 변경)
• 원본 리스트 변경됨
• 리스트(list)만 가능
• lst.sort()

7. Conclusion

• sorted() 또는 리스크 컴프리핸션를 이용한 정렬을 통해 문제를 해결할 수 있습니다.