[LeetCode] - 977. Squares of a Sorted Array

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Squares of a Sorted Array" 문제입니다.

--> https://leetcode.com/problems/squares-of-a-sorted-array/description/

 

문제 : 

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 <= 10^4
• -10^4 <= nums[i] <= 10^4
• 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?

---

이 문제를 직역하자면, 주어진 정렬된 정수 배열 nums에서 각 요소의 제곱을 계산하고, 그 결과를 다시 비내림차순으로 정렬된 배열로 반환해야 합니다. 또한, O(n) 시간 복잡도로 해결할 수 있는 방법을 찾아보는 걸 권장하는 문제입니다.

 

1. 재이의 코드 :

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

주어진 정렬된 정수 배열 nums에서 각 요소의 제곱을 계산하고, 그 결과를 다시 비내림차순으로 정렬된 배열로 반환하세요. 예를 들어, 입력이 [-4,-1,0,3,10]이면 출력은 [0,1,9,16,100]입니다. 이 문제는 O(n) 시간 복잡도로 해결할 수 있는 방법을 찾아보세요.

 

위 코드는 반복문을 통해서 nums들의 요소를 자신의 제곱으로 바꿔넣고, 반복문이 끝나면은 nums를 sort 하는 코드인데, 사실 이 코드는 반칙을 쓴 코드입니다. 왜냐하면 Follow-Up에서는 O(n)인 코드를 써보라고 제시하였는데도 불구하고 Arrays.sort() 메소드를 써서 결국은 O(nlogn) 코드가 되었기 때문입니다. 그래서 밑에서 다른 유저의 모범답안을 다뤄보려고 합니다. 

---

2. 모범답안 : 

class Solution {
    public int[] sortedSquares(int[] arr) {
        int n = arr.length;
        int ans[] = new int[n];
        int idx = n-1;
        int i=0,j=n-1;

        while(i<=j){
            if(Math.abs(arr[i])>Math.abs(arr[j])){
                ans[idx--] = arr[i]*arr[i];
                i++;
            }else{
                ans[idx--] = arr[j]*arr[j];
                j--;
            }
        }
        return ans;
    }
}
// ravikumar50 유저의 코드

 

이 분은 Two Pointer 방법을 사용했습니다. 제가 반칙을 써서 코드를 쓴 만큼, 벌로 이 코드를 더 연구해서 상세하게 설명을 드리고자 합니다. 

 

• 변수 초기화:
  • n은 입력 배열의 길이를 나타내고,
  • ans는 결과 배열을 저장할 배열입니다.
  • idx는 결과 배열에서 값을 채울 인덱스이며,
  • i는 왼쪽 포인터, 즉 처음에는 배열의 시작을 가리킵니다.
  • j는 오른쪽 포인터, 처음에는 배열의 마지막을 가리킵니.
• 두 포인터를 사용한 반복문:
  • while (i <= j) : 두 포인터가 교차하지 않을 때까지 반복합니다.
  • if (Math.abs(arr[i]) > Math.abs(arr[j])) : 만약에 왼쪽 포인터가 가리키는 값의 절대값(마이너스 고려) 이 오른쪽 포인터가 가리키는 값의 절댓값보다 큰 경우에는 :
    • ans[idx--] = arr[i] * arr[i]; : 더 큰 값의 제곱을 결과 배열의 현재 인덱스(idx)에 저장하고, 인덱스를 감소시킵니다.
    • i++: 왼쪽 포인터를 오른쪽으로 이동합니다.
  • else : 아닐 때는, 오른쪽 포인터가 가리키는 값의 절댓값이 왼쪽 포인터의 절댓값보다 크거나 같은 경우:
    • ans[idx--] = arr[j] * arr[j]; : 더 큰 값의 제곱을 결과 배열의 현재 인덱스(idx)에 저장하고, 인덱스를 감소시킵니다.
    • j-- : 오른쪽 포인터를 왼쪽으로 이동합니다.
  • 그럼 이제 결과를 리턴하면 끝 ! 시간 복잡도 O(n) 코드가 되는 겁니다

 

 

 

1,2 번 코드 Runtime 결과