[C++] LeetCode (릿코드) 977 : Squares of a Sorted Array

문제

Loading... (leetcode.com)

Squares of a Sorted Array - LeetCode

코드

class Solution
{
    public:
        vector<int> sortedSquares(vector<int> &nums)
        {
            for (int &i: nums)
            {
                i *= i;
            }

            vector<int> res(nums.size());
            int idx = nums.size() - 1;
            int lo = 0;
            int hi = nums.size() - 1;

            while (idx != -1)
            {
                res[idx--] = (nums[lo] < nums[hi]) ? nums[hi--] : nums[lo++];
            }
            return res;
        }
};

설명

벡터의 모든 수를 제곱하여 오름차순으로 정렬하는 문제이다.
문제 설명을 그대로 따라가면 O(n log n)으로 해결할 수 있는데, 투 포인터 알고리즘을 사용하면 O(n)만으로 해결할 수 있다.

먼저 벡터의 모든 수를 제곱한다.
그 후, 처음 수 lo와 마지막 수 hi를 비교한다.
lo나 hi 둘 중의 값은 최댓값이다. 둘 중 큰 값을 결과값 벡터 res의 마지막에 저장하고,
해당하는 lo 혹은 hi를 중앙 쪽으로 한 칸씩 포인터를 이동시킨다.
이렇게 하면 res에는 제곱의 값이 최댓값이 끝부터 채워지기 때문에 오름차순으로 정렬된 것과 같다.