[2024] day 63. Leetcode 977. Squares of a Sorted Array

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 2일 (토)
Leetcode daily problem

977. Squares of a Sorted Array

https://leetcode.com/problems/squares-of-a-sorted-array/description/?envType=daily-question&envId=2024-03-02

Problem

int형 문자열 원소로 구성돼 오름차순으로 정렬된 배열 nums가 주어질 때 해당 배열의 원소에 제곱한 수들을 오름차순으로 정렬해 반환한다.
조건 : 시간복잡도 O(n)

Solution

Array, two pointer

가장 간단한 방법은 brute force로 O(nlogn) 으로 가능하다. 주어진 리스트(nums)의 원소인 문자열을 한번 탐색하면서 제곱하고, 제곱했던 리스트를 정렬하면 O(nlogn)이 소요된다.

O(n)으로 해결하기 위해서는
left, right 투 포인터를 사용하는데 left로는 리스트의 첫 인덱스 right로는 리스트 마지막 인덱스로 초기화한다.

재정렬해서 반환할 리스트를 주어진 nums와 같은 사이즈를 가진 리스트로 초기화한다.
위의 초기화된 리스트에 순차적으로 값을 업데이트 하는데,
업데이트 될 값은 nums 배열의 left, right의 인덱스 값의 원소를 제곱한 값을 비교했을 때 더 큰 수이다.

비교 시 left 인덱스의 원소가 크면 해당 원소를 리스트에 업데이트하고 left 인덱스를 +1 해서 오른쪽으로 이동한다.
반대로 right 인덱스의 원소가 크면 해당 원소를 리스트에 업데이트 하고 right -1로 왼쪽으로 이동한다.

Code

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        result = [0] * len(nums)
        left, right = 0, len(nums)-1

        for i in range(len(nums)-1, -1, -1):
            if abs(nums[left]) > abs(nums[right]):
                result[i] = nums[left] **2
                left +=1
            else:
                result[i] = nums[right] **2
                right -=1

        return result

Complexicity

시간 복잡도

주어진 배열을 탐색할 때 O(n)이 소요되어 시간복잡도는 O(n)이다.

공간 복잡도

주어진 배열 A 사이즈 만큼 배열을 생성하므로 O(n)의 공간복잡도이다.