[LeetCode] Arrays101 - Squares of a Sorted Array

아주 오랜만에 다시 시작한 알고리즘 문제 풀기!

(그동안 노션으로 휘리릭~ 간단하게 정리하는 것에 맛들려서 블로그에 손을 안댔는데 매우 반성하고 있다. 하하...)

---

Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

 

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

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

 

Constraints:

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

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

 

---

 

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var squareNum = function(num) {
    return Math.abs(num) ** 2;
};

var sortedSquares = function(nums) {
    return nums.map(squareNum).sort((l, r) => l - r)
};

 

처음에는 일단 (시간 복잡도가 O(n)이 되도록 하라는) 문제의 요구사항을 무시하고 일단 되는대로 풀었다.

물론 이렇게만 해도 통과된다ㅋㅋ

 

그치만 문제의 요구사항은 그게 아니라는걸 아니까 진짜 머리가 터지도록 고민을 했는데

아무리 생각해도 도저히 번뜩이는 아이디어가 떠오르지 않았다...

(하 이럴때마다 스스로가 너무 바보같음 ㅠㅠ)

 

그래서 힌트라도 얻을겸 구글링을 해보니 정말 간단하면서도 싱크빅같은 방법이 있었다.

(왜 생각해내지 못했을까 흑흑ㅜㅜ)

 

 

숫자를 절대값으로 만들어서 생각해보면 양쪽 끝의 숫자들은 크기가 크고 안쪽으로 가면서 작아진다는 것에서 착안한 방법이다.

 

이렇게 양쪽 끝의 값들을 비교해서 크기가 큰 값으로 배열의 끝에서부터 채워나가면 된다.

이걸 코드로 만들면 아래와 같다.

 

var squareNum = function(num) {
    return Math.abs(num) ** 2;
};

var sortedSquares = function(nums) {
    const result = [];
    let start = 0;
    let end = nums.length - 1;
    let position = nums.length - 1;
    
    while (position >= 0) {
        if (squareNum(nums[start]) < squareNum(nums[end])) {
            result[position--] = squareNum(nums[end--]);
        } else {
            result[position--] = squareNum(nums[start++]);
        } 
    }
    
    return result;
};

 

 

Reference

javascript.plainenglish.io/javascript-algorithm-how-to-square-a-sorted-array-f2410580aa09

JavaScript Algorithm: How to Square a Sorted Array