Question

• 오름차순으로 된 배열의 인덱스를 제곱하여 오름차순으로 출력하시오

풀이

풀이 1 - sort

간단하게 제곱한 후 sort 라이브러리를 이용해 정렬하여 리턴하는 방식이다.

class Solution {
public:    
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i=0; i<nums.size(); i++){
            nums[i]*= nums[i];
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};

풀이 2 - two pointer

주어진 벡터의 left 와 right 포인터를 두고 그 값을 서로 비교하며 더 큰 값을 새로운 배열에 저장한다.

class Solution {
public:    
    vector<int> sortedSquares(vector<int>& nums) {
        int n=nums.size();
        int left=0; int right=n-1;

        vector<int> sorted(n);
        int pos = n-1;

        while(left<=right){ //-4,-1,0,3,10
            if(abs(nums[left])<abs(nums[right])){
                sorted[pos--] = pow(nums[right], 2); right--;
            }
            else { // 1 9 16 100
                sorted[pos--] = pow(nums[left], 2); left++;
            }
        }
        return sorted;
    }
};

참고

• https://butter-shower.tistory.com/226