[LeetCode] 977. Squares of a Sorted Array, Easy

1. 문제

• 오름차순으로 정렬된 배열이 주어질 때, 각 요소를 제곱한 뒤에도 오름차순을 유지하는 배열을 반환하라.

2. 해결

function sortedSquares(nums: number[]): number[] {
    const result = nums.map(num => Math.pow(num, 2))
        
    result.sort((a,b) => a-b);
    
    return result;
};

• 우선, 문제를 보자마자 떠올린 방법이다. 단순히 모든 배열을 순환하며 제곱하고, 해당 배열을 정렬한다.
• 이 경우, O(NlogN) 시간 복잡도가 나온다.

function sortedSquares(nums: number[]): number[] {
    const result = new Array(nums.length) // 1. 결과를 담을 배열.
    let left = 0, right = nums.length -1, index = nums.length -1; // 각 포인터 및 인덱스.

    while(left <= right) { // 2. 두 포인터가 만날 때 까지 반복.
        const leftVal = Math.pow(nums[left],2);
        const rightVal = Math.pow(nums[right],2);
		
        // 3. 두 포인터의 제곱값 중 큰 값을 현재 인덱스에 넣고 포인터 조정.
        if(rightVal >= leftVal) {   
            result[index] = rightVal;
            right-=1;
        } else {
            result[index] = leftVal;
            left+=1;
        }

        index--;
    }

    return result;
};

• 다른 사람들의 풀이 방법 중, 투 포인터를 이용한 방법이 있길래 사용해봤다.
• 원리는, 배열의 시작과 끝에 포인터를 두고 두 포인터가 만날 때 까지 각 포인터의 제곱값을 비교하여 마지막 요소부터 채우는 것.
• 내가 첫 번째 방법으로 생각한 이유는? 
  • -121, 1, 2 ,11 다음과 같이 오름차순 배열이 주어지면, -121의 제곱값이 가장 크므로 맨 뒤에 위치해야 한다.
  • 그러니깐, 제곱하고 다시 정렬을 해줘야 겠구나.
• 근데 두 번째 방법이 가능한 이유는?
  • 애초에 오름차순 정렬된 배열이 주어지기 때문.
  • 결과 배열의 마지막 요소가 바뀔 가능성은? 첫 번째 요소부터 제곱값이 큰 경우.
  • 그럼 첫 번째 요소부터 제곱값을 비교해가며 값을 채운다.

Reference

• https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md

Ready-For-Tech-Interview/Algorithm/투포인터 알고리즘.md at master · WooVictory/Ready-For-Tech-Interview