Squares of a Sorted Array

977. Squares of a Sorted Array

문제

문제는 이미 정렬된 배열의 모든 요소를 제곱하여 재졍렬하는 문제이다. 각 요소를 제곱하고 정렬하는 방법은 쉽게 작성할 수 있지만, 문제에서는 O(n)의 시간복잡도라는 조건이 주어졌다.

테스트 케이스

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

제곱을 한 후의 `nums` 배열은 [16,1,0,9,100],
다시 정렬을 하면 [0,1,9,16,100]가 된다.

풀이

앞서 이분탐색 중 배열의 모든 요소를 탐색하는 방법이다.
left와 right 인덱스 포인터를 하나씩 옮겨가면서 nums[left]의 제곱한 값과 nums[right]의 제곱한 값 중 더 큰 값을 새로운 배열인 result에 추가(unshift)해 준다.

시간 복잡도 O(n)과 공간복잡도 O(n)이다.

var sortedSquares = function(nums) {
  let result = []
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    let leftSquared = nums[left] ** 2;
    let rightSquared = nums[right] ** 2;

    if (leftSquared > rightSquared) {
      result.unshift(leftSquared)
      left++
    } else {
      result.unshift(rightSquared)
      right--
    }
  }
  
  return result;
};

풀이처럼 제곱→정렬의 순서대로 했지만, `Math.abs() 절대값으로 비교하여 정렬→제곱으로 순으로도 해결할 수 있을 것 같다.

비슷한 유형의 문제를 계속 풀다보니 이제 감이 좀 잡히는 듯 하다.