Squares of a Sorted Array

문제

전제
내림차순으로 정렬된 Integer 배열 nums의 값들을 제곱하여 내림차순 정렬 후 반환해줍니다.

예제1

입력: nums = [-4,-1,0,3,10]
출력: [0,1,9,16,100]
설명 : 제곱 후 배열 [16,1,0,9,100].
정렬 후 배열 [0,1,9,16,100].

예제2

입력: nums = [-7,-3,2,3,11]
출력: [4,9,9,49,121]

제약 조건

1 <= nums.length <= 100000
-100000 <= nums[i] <= 100000
nums변수는 내림차순으로 정렬되어있다.

---

Solution

배열의 값을 제곱 후 정렬하는 것은 간단하다

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

하지만 Arrays.sort()를 사용하지 않고 다른 방식으로 풀어보았다.

나의 풀이

class Solution {
    public int[] sortedSquares(int[] nums) {
		int[] result = new int[nums.length];
		int left = 0, 			 	    i = 0;
		int right = nums.length - 1, 	index = nums.length - 1;
		
		while(i <= nums.length - 1){
			if(Math.abs(nums[left]) > Math.abs(nums[right])) {
				result[index] = nums[left] * nums[left]; 
				left++;	
			}else {
				result[index] = nums[right] * nums[right]; 
				right--;
			}
			index--;
            i++;
		}
		return result;
    }
}

Runtime: 2 ms
Memory Usage: 56 MB

잘 풀리지 않아 다들 어떻게 풀었나 검색해봤는데 배열의 왼쪽 값과 오른쪽 값을 비교해서 sort해주는 풀이가 제일 많았습니다.

nums가 갖고있는 최대 index만큼 루프를 동작시키면서 Math.abs()로 배열의 왼쪽과 오른쪽의 절대 값을 비교합니다. 절대 값을 비교하는 이유는 제곱이기 때문에 결과 값에는 자연수만 존재하기 때문입니다.

두 값을 비교해 더 큰 값을 배열의 마지막, 오른쪽 부터 값을 채워나가며 정렬이 됩니다.

위와 비슷한 로직으로 Math.abs를 사용하지 않고 배열의 값을 모두 제곱을 한 뒤 비교해가며 값을 채워나가는 방식도 좋을 것 같습니다.