Leetcode - 977. Squares of a Sorted Array

문제

주어진 배열의 값을 제곱한 결과를 오름차순 정렬하라.

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

해결 O(nlogn)

일단 시키는 대로 푼 방법.

int cmp(const int *a, const int *b)
{
    return *(int *)a - *(int *)b;
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortedSquares(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    for (int i = 0; i < numsSize; i++)
        nums[i] = nums[i] * nums[i];
    qsort(nums, numsSize, sizeof(int), cmp);
    return nums;
}

해결 O(n)

근데 O(n)해결이 가능하다고 함. 좀 더 고민해보기.
생각해보면 제곱을 했을때 중앙을 기준으로 양옆으로 오름차순 정렬되어있는셈. 따라서 투포인터를 통해서 리턴배열에 추가한다.

조각조각 정렬이 되어있을지라도 어쨋든 정렬이 되어있다면 logN이 아니라 N에 해결이 가능. 이런 문제는 주로 투포인터로 해결할수있을듯.

input이 이미 정렬이 되어있다는것은 아주 강력한 단서다. 문제에서 어떻게든 활용해야한다. O(N) 으로 해결이 가능한경우가 많으니 솔루션을 더 고민해보기

/*
-4 -1 2 3 10
      ^
-4  -2 -1 3 
          ^
-5 -4 -3 -2 -1
                ^
1 2 3 4 5
^
*/
#include <stdlib.h>
int* sortedSquares(int* nums, int numsSize, int* returnSize){
    int pos = 0, left = 0, right = 0, retcnt = 0;
    *returnSize = numsSize;
    if (numsSize == 1) {
        nums[0] = nums[0] * nums[0];
        return nums;
    }
    int * ret = (int *)calloc(numsSize, sizeof(int));
    
    /* find left, right position */
    for (; pos < numsSize; pos++) {
        if (nums[pos] >= 0)
            break;
    }
    if (pos == 0) {
        left = 0;
        right = left + 1;
    } else if (pos == numsSize) {
        right = numsSize - 1;
        left = right - 1;
    } else {
        left = pos - 1;
        right = pos;
    }
    
    /* make squre of nums[] */
    for (int i = 0; i < numsSize; i++)
        nums[i] = nums[i] * nums[i];
    
    /* make a new sorted array from two pointer */
    while (1) {
        if (nums[left] == INT_MAX && nums[right] == INT_MAX)
            break;
        if (nums[left] < nums[right]) {
            ret[retcnt++] = nums[left];
            if (left == 0)
                nums[left] = INT_MAX;
            else
                left--;
        } else {
            ret[retcnt++] = nums[right];
            if (right == numsSize - 1)
                nums[right] = INT_MAX;
            else
                right++;
        }
            
    }
    return ret;
}