[LeetCode] Squares of a Sorted Array

목차

문제

• 정렬된 int 배열이 주어졌을 때, 각 원소를 제곱한 값에 대해 정렬(오름차순)된 상태를 반환하시오.
• 예시

  • Input: nums = [-4,-1,0,3,10]
    Output: [0,1,9,16,100]

  • Input: nums = [-7,-3,2,3,11]
    Output: [4,9,9,49,121]

• 제약조건
  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in non-decreasing order.

문제 풀이

풀이 1 : 정렬

• 풀이
  • 단순하게 모든 값들을 제곱한 뒤에 정렬을 해주면 됩니다.
• 코드

  • class Solution(object):
        def sortedSquares(self, A):
            return sorted(x*x for x in A)

• 시간복잡도
  • 각 원소를 제곱하는 시간복잡도는 O(N) 
  • 정렬의 경우 시간복잡도 O(NlogN)
  • 따라서 전체 시간복잡도는 O(NlogN)이 됩니다.

풀이 2 : 투포인터

• 풀이
  • nums는 현재 정렬된 상태입니다. 이때 이제 음수를 제곱할 경우에는 제일 작은 값이 제일 크게 될 것이고, 양수를 제곱할 경우에는 제일 큰 값이 제일 크게 될 것입니다.
  • 이를 생각한다면 제일 왼쪽 값과 제일 오른쪽 값을 비교하여 더 큰 값을 result의 제일 오른쪽부터 채워주는 방식을 적용하면 됩니다.
• 코드

  • class Solution(object):
        def sortedSquares(self, nums):
            n = len(nums)
            result = [0 for _ in range(n)] 
            left = 0
            right = n-1
            for i in reversed(range(0,n)):
                if abs(nums[left]) < abs(nums[right]):
                    square = nums[right]**2
                    right -= 1
                else:
                    square = nums[left]**2
                    left +=1
                result[i] = square
                
            return result

• 시간복잡도
  • 다른 정렬 없이 하나의 for문을 통해 해결하기 때문에 O(N)만에 해결가능합니다.
  • 투포인터를 사용하면 정렬을 하지 않기 때문에 O(N)만에 해결이 됩니다.

알게 된 내용

• 정렬 알고리즘을 사용하지 않고 규칙을 찾아 투포인터를 이용한다면 정렬을 하기 위한 O(NlogN)의 시간복잡도가 O(N)만에 해결이 가능합니다.
  • 투포인터는 두 개의 정렬된 배열이 있을때 효율적인 문제입니다. (또는 한 배열이 정렬되어 있을때, 처음과 끝을 투포인터로 잡고 푸는 문제도 존재합니다.)

출처

• https://leetcode.com/explore/learn/card/fun-with-arrays/521/introduction/3240/