LeetCode 977(Squares of a Sorted Array, java)

0. 문제

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

Squares of a Sorted Array - LeetCode

 

1. 문제 설명

- 문제에서 정수형 배열(nums)이 주어진다.

- 정수형 배열의 모든 요소의 제곱을 배열에 저장하고 이를 오름차순으로 반환하는 것이 문제의 핵심이다.

 

2. 문제 해설

a) 첫 번째 접근

- 가장 간단한 해결 방법은 for문을 사용하여 원소에 접근하는 것이다.

- 접근한 원소의 제곱을 구하고 Arrays 라이브러리의 sort() 메서드를 이용하여 정리한다.

- 그러나 이 방법은 시간 복잡도 측면에서 그렇게 우수하지는 않다.

- 그렇다면 시간 복잡도를 최소화할 수 있는 방법은 무엇일까?

 

b) 두 번째 접근

- while 반복문과 three pointers 방법을 사용하면 시간 복잡도를 최소화할 수 있다.

- 준비할 변수는 다음과 같다.

- 첫 번째 pointer는 가장 첫 번째 원소의 위치를 가리킨다.

- 두 번째 pointer는 가장 마지막 원소의 위치를 가리킨다.

- 세 번째 pointer는 배열을 탐색하기 위한 것으로, 가장 마지막 원소의 위치를 가리킨다.

- 그리고 제곱된 원소의 값을 저장할 배열(= result)을 생성한다.

 

c) 세 번째 접근

- 가장 첫 번째 원소와 가장 마지막 원소의 제곱을 구한다.

- 이 둘을 비교하여 더 큰 제곱을 가지는 값을 result의 가장 마지막 위치에 저장한다.

 

- result의 마지막 위치에 저장하는 이유는 기존의 배열(nums)이 오름차순으로 정렬되어 있기 때문이다.

- 가장 첫 번째 원소의 제곱이 가장 마지막 원소의 제곱보다 크다면 앞으로도 계속 앞쪽에 위치한 원소의 제곱이 

   뒤쪽에 위치한 원소의 제곱보다 클 가능성이 있기 때문이다. 

 

- 첫 번째 원소의 제곱이 마지막 원소의 제곱보다 더 큰 경우, 첫 번째 원소의 위치를 가리키는 pointer를 1 증가시킨다.

- 반대의 경우 마지막 원소의 위치를 가리키는 pointer를 1 감소시킨다.

 

- 이와 같은 방식을 문제에서 주어진 배열(nums)의 길이만큼 반복하여 수행한다.

- 다음 코드를 보면서 이해해보자.   

 

3. 정답 코드

a) for 반복문

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;
    }
}

 

b) while + pointers

class Solution {
    public int[] sortedSquares(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        int idx = nums.length - 1;
        int[] result = new int[nums.length];
        
        while(start <= end) {
            int a = nums[start] * nums[start];
            int b = nums[end] * nums[end];
            
            if(a > b) {
                result[idx] = a;
                idx--;
                start++;
            }
            
            else {
                result[idx] = b;
                idx--;
                end--;
            }
        }
        return result;
    }
}