Leetcode 977. Squares of a Sorted Array - Two Pointers

오늘도 어김없이 리트코드!

 

오늘은 Two Pointers 문제에 대하여 다루어보았다.

Two Pointers 주제에 있길래 원하시는대로 Two Pointers를 설정하였다.

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [0] * n
        # Two pointers
        low = 0
        high = n - 1
        for i in range(n - 1, -1, -1): # 반대로 순회하면서 비교
            if abs(nums[low]) > abs(nums[high]):
                answer[i] = nums[low] * nums[low]
                low += 1
            else:
                answer[i] = nums[high] * nums[high]
                high -= 1
        return answer

여기서 pointer는 low, high 두개이다.

for문에서 반대로 순회하면서 비교하고, 어차피 square을 비교해야하므로 abs로 비교해주었다(nums[low] ** 2 해도 될것같아 근데 그냥...)

 

여기서 이게 가능한 이유는?

- 바로! nums가 sorted list이기 때문이다.

음의 정수 부분, 양의 정수 부분이 각각 sorted된 두개의 list라고 생각을 해보면 abs를 비교하여 그냥 정렬하기만 하면 되는 것이다. (merge sort의 마지막 merge느낌이랄까 ㅎ)

 

 

faster than 93.18%라니! Yeah 신닌다

Time Complexity : O(n)

Memory Complexity : O(n) -> nums와 같은 크기의 리스트를 하나 만들어야 해서 이것은 바로 big extra space가 된다 .. In place로 하면 좋으련만 흑흑

 

여튼 오늘도 코딩 연습 끝!

 

뿌-듯