[LeetCode] 360. Sort Transformed Array

 A quadratic function(2차 함수)에 계수로 a와 b가 주어지고 y절편(y-intercept)으로 c가 주어지고, 정렬된 리스트(nums)가 주어진다. 이때 input에 따른 2차 함수의 output으로 이뤄진 리스트를 정렬해 반환해야된다. 이때 시간복잡도는 O(n)을 만족해야한다.

 

 예시:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

 

 시간복잡도를 고려하지 않으면 간단한 정렬 알고리즘을 통해 O(n logn)의 시간복잡도로 정답을 얻을 수 있지만. O(n)의 시간복잡도를 만족하려면 주어진 리스트(nums)가 정렬됐다는 것과 2차 함수의 특징을 이용하면 된다. 2차 함수는 꼭지점을 중심으로 꼭지점으로부터의 x의 거리가 멀어질 수록 y가 커지거나(a가 양수 일 때) 작아지는(a가 음수 일 때) 특징을 갖는다. a가 0일 경우는 이미 input이 정렬됐기에 b가 양수면 함수에 따를 결과값만 그대로 저장해 반환하거나 b가 음수면 이를 거꾸로 반환하면 된다.

 

class Solution:
    def quad(self, a, b, c, x):
        return a * x * x + b * x + c

    def sortTransformedArray(self, nums: List[int], a: int, b: int, c: int) -> List[int]:
        retL = []
        if a == 0:
            for n in nums:
                retL.append(self.quad(a, b, c, n))
            if b >= 0:
                return retL
            else:
                return retL[::-1]
        else:
            numsD = [0 for i in range(len(nums))]
            center = -b / a / 2
            for i, n in enumerate(nums):
                numsD[i] = n - center
            l, r = 0, len(nums)-1
            
            while l < r:
                if abs(numsD[l]) > abs(numsD[r]):
                    cur = self.quad(a, b, c, nums[l])
                    l += 1
                else:
                    cur = self.quad(a, b, c, nums[r])
                    r -= 1
                retL.append(cur)
            retL.append(self.quad(a, b, c, nums[r]))
            
            if a > 0:
                return retL[::-1]
            else:
                return retL