[leetcode] 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.

이번 문제는 감소하지 않는 순서로 정렬되어 있는 nums라는 정수 배열이 주어지고,
각 숫자의 제곱이 감소하지 않는 순서로 정렬되어 있는 배열을 반환하는 것이다.

풀이 접근 방식

이번 문제에서는 two pointers 방식을 사용했다.
주어진 배열 nums의 첫번째 index를 left, 마지막 index를 right라고 하고, 반환해야 할 값을 담은 정수 배열을 answer라고 하자.

배열의 범위는 정수이기 때문에 left의 위치한 숫자가 음수일 수도 있고 right에 위치한 숫자보다 절댓값이 더 클 수도 있다. 예를들어, nums = [-4,-1,0,2,3]라는 배열이 주어졌다고 가정을 해보자. -4는 3보다는 작지만 -4의 절댓값은 3의 절댓값 보다는 더 크다. 따라서, 주어진 배열이 단순히 감소하지 않는 순서로 정렬 되어 있다고 해서, 반환할 배열을 index 0부터 순서대로 채우는 것은 answer = [16,1,0,4,9]이라는 틀린 값을 반환 할 것이다.

따라서, two pointers를 이용하여, left에 위치한 숫자의 절댓값과 right에 위치한 숫자의 절댓값을 비교하여 그 절댓값이 더 큰 숫자의 제곱값을 answer의 가장 마지막 index부터 순서대로 넣어준다.

이 과정은 for loop을 이용하여, left와 right의 숫자들을 비교하고 answer에 넣어준 값의 index가 left면 증가, 혹은 right면 감소시키는 과정을 반복한다.

시간 및 공간 복잡도

이 풀이 방식의 시간 복잡도는 O(n)이다. 왜냐하면, 두 숫자의 절댓값 비교는 O(1)이 걸리고 이 과정을 n번 반복하기 때문에 O(1) * n = O(n)이기 때문이다.

이 풀이 방식의 공간 복잡도는, 풀이한 값을 저장한 배열인 answer를 포함시키면 O(n)의 공간을 필요로하고, 이를 포함시키지 않고 오로지 문제를 푸는데 필요한 공간만을 계산할 시에는 두개의 index를 저장할 공간만을 필요로 하기에 오로지 O(1)만큼의 공간을 필요로 한다.

혹시 이게 학교 과제였다면, 나는 answer에 값을 저장해서 반환하는 것 까지가 문제라고 판단하여 O(n)가 이 문제의 공간 복잡도라고 답을 적어 낼 것이다.

소스코드

class Solution {
    public int[] sortedSquares(int[] nums) {
        
        int n = nums.length;
        int[] answer = new int[n];
        int left = 0, right = n - 1;
        
        for (int i = n - 1; i >= 0; i--) {
            
            int square;
            
            // abs(left) > abs(right)
            if(Math.abs(nums[left]) < Math.abs(nums[right])) {
                square = (int) Math.pow(nums[right], 2);
                right --;
            } 
            // abs(left) <= abs(right)
            else {
                square = (int) Math.pow(nums[left], 2);
                left ++;
            }
            
            answer[i] = square;
        }
        
        return answer;
    }
}