[leetcode] 977. Squares of a Sorted Array

 

Explore - LeetCode

[Success]

내림차순으로 정렬된 정수 배열이 주어졌을 때, 내림차순으로 정렬된 각 인덱스 값의 제곱 구하는 문제

 

 

 

[풀이]

각 인덱스의 값의 제곱을 구한 후 해당 인덱스에 다시 할당시킨다. 

제곱의 값으로 다 채워진 후에는 해당 배열을 내림차순으로 정렬.

class Solution {
    public int[] sortedSquares(int[] nums) {
        
        for (int i=0; i<nums.length; i++) {
            int square = nums[i] * nums[i];
            nums[i] = square;
        }
        
        Arrays.sort(nums);
        
        return nums;
    }
}

 

 

 

[leetcode solution]

[-10, -5, 1, 2, 4, 7] 배열이 주어졌을때 해당 값들을 제곱하여 재할당하면 [100, 25, 1, 4, 16, 49] 의 값으로 세팅된다. 

이를 다시 내림차순으로 정렬하면 [1, 4, 16, 25, 49, 100] 

이 때 제곱하여 재할당하는 시간복잡도는 O(n) , 내림차순으로 정렬하는 시간복잡도는 O(n log n) 의 비용이 들어간다. 

 

위 방법이 아닌 Two-Point 방법으로 접근하면 시간복잡도를 O(n) 으로 해결 할 수 있다. 

 

1. 제곱의 수를 새롭게 할당할 배열을 하나 선언한 후 nums 배열을 뒤에서 부터 접근한다. 

2. 첫번째 값과 마지막 값에 각각의 left 와 right 라는 포인터를 두고 비교를 하는데 이 때 절대값으로 비교를 하고 left 와 right 중 어느 수를 제곱할지를 결정한 후에 포인터 이동을 시켜준다. 

3. 제곱대상이 된 수를 제곱을 해준 후 새로운 배열에 뒤에서 부터 할당시켜주면 내림차순으로 완성 될 수 있다.

 

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0;
        int right = n - 1;

        for (int i = n - 1; i >= 0; i--) {
            int square;
            if (Math.abs(nums[left]) < Math.abs(nums[right])) {
                square = nums[right];
                right--;
            } else {
                square = nums[left];
                left++;
            }
            result[i] = square * square;
        }
        return result;
    }
}