977. Squares of a Sorted Array

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        for(int i=0; i<nums.length; i++){
            result[i] = nums[i]*nums[i];
        }
        
        int small =0;
        for(int k = result.length; k>0; k--){
            for(int j = 0; j<= k-2; j++){
                if(result[j] > result[k-1]){
                    small = result[k-1];
                    result[k-1] = result[j];
                    result[j] = small;
                }
            }
        }
        
        return result;
    }
}

먼저, 각 원소를 제곱하여 새로운 배열 result에 저장하는 부분은 O(n) 시간이 걸립니다. 여기서 n은 nums 배열의 길이입니다.

그 다음, 정렬 부분은 버블 정렬 알고리즘을 사용하고 있습니다. 버블 정렬의 최악의 경우 시간 복잡도는 O(n^2)입니다. 이 부분에서 두 개의 반복문을 사용하므로, 전체 시간 복잡도는 O(n^2)입니다.

따라서 주어진 코드의 시간 복잡도는 O(n) + O(n^2)로 요약할 수 있습니다.
O(n^2)의 영향력이 크기 때문에 전체 시간 복잡도는 O(n^2)입니다.

Accepted는 되었지만 문제에서는 O(n)의 solution을 원했기에 다른 접근이 필요해 보인다.