977. Squares of a Sorted Array

mmmYoung·2022년 3월 13일

리트코드

목록 보기

8/21

문제 설명

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

정수형 배열 nums가 감소하지 않는 순서로 주어진다. 각 원소의 제곱 값을 감소하지 않는 순서로 출력하여라. 새로운 접근을 이용해 시간복잡도 O(n)의 방법을 찾아보자.

출력 예시

접근 방법

첫번째 시도

단순히 answer 벡터에 제곱 값 삽입 후 sort 하기...
이지만 출제자가 원하는 방법은 아님을 직감.

두번째 시도

제곱을 하면서 바로 원하는 위치에 삽입하는 방법(=O(n)의 방법) 생각하기. 이미 정렬된 배열이므로 제곱을 했을 때 가장 큰 수는 필연적으로 첫번째 인덱스 또는 마지막 인덱스이다.
따라서 start와 end를 이용해 맨 앞과 맨 뒤 배열을 시작으로 중앙까지 차례대로 비교한다면 배열을 한 번만 탐색하면서 해결할 수 있다.

소스코드

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector <int> answer(nums.size());
        int end = nums.size()-1;
        int start=0;
        int idx = end;
        
        while(start <= end){
            if(nums[start] < 0) nums[start]*=-1; 
            if(nums[end]<0) nums[end]*=-1;
            
            if(nums[start] <= nums[end]){
                answer[idx]=nums[end]*nums[end];
                end-=1;
            }
            else{
                answer[idx]=nums[start]*nums[start];
                start+=1;
            }
            idx--;
        }
        
        return answer;
    }
};