Squares of a Sorted Array (C++)

https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/3574/

Explore - LeetCode

드디어 모든 것을 마무리 하고 정말로 돌아왔습니다!! 

 해당 문제는 LeetCode - Explore - Array 중 Conclusuion 마지막 문제입니다. 이 문제는 특이하게 난이도와 넘버가 없고, 문제를 다 푼 이후에도 다른 사람들의 코드를 볼 수가 없었네요. 아쉽게도ㅠ

 문제의 조건 중 핵심 사항들을 정리하면 아래와 같습니다.

▶  nums라는 int형 배열(vector)가 입력 되면, 각 원소들을 제곱한 뒤 non-decreasing order(오름차순) 배열로 return

▶ 입력되는 배열 nums의 조건

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in non-decreasing order.

▶ Example

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

 

◈ 문제 풀이 방법

 - 입력된 배열 nums내 입력된 음수들은 내림차순, 양수들은 오름차순으로 정렬이 된 상태

 - 양수가 시작되는 인덱스와 음수가 끝나는 포인트의 인덱스를 저장

 - 두 인덱스의 배열 값을 비교하여 오름차순으로 정렬 후 임의의 vector에 결과로 저장

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        
        vector<int> vecResult;
        int nPositiveStart = nums.size();
        int nNegativeEnd = 0;
        int nTemp = 0;
        
        bool bOnlyNegative = true;

        for(int i = 0 ; i < nums.size(); i++) {
            if(nums[i] >= 0) {
                nPositiveStart = i;
                nNegativeEnd = i-1;
                
                bOnlyNegative = false;
                break;          
            }
        }
        
        if(bOnlyNegative)
            nNegativeEnd = nums.size()-1;
        
        for (int i = 0; i < nums.size(); i++) {
            if(nNegativeEnd < 0)
                vecResult.push_back(nums[nPositiveStart++]);
            else if(nPositiveStart > nums.size() -1)
                vecResult.push_back(nums[nNegativeEnd--]);
            else {
                if(nums[nNegativeEnd] * -1 < nums[nPositiveStart])
                    vecResult.push_back(nums[nNegativeEnd--]);
                else
                    vecResult.push_back(nums[nPositiveStart++]);
            }
        }
        
        for (int i = 0 ; i < vecResult.size(); i++)
            vecResult[i] *= vecResult[i];
        
        return vecResult;
    }
};

 

 처음에 그냥 다 비교해서 정렬하는 방법으로 구현을 해보았는데 역시나 타임 아웃이 발생해서, 양수가 시작되는 인덱스를 찾아 저장 후, 음수가 끝나는 인덱스 또한 저장하여 음수 인덱스는 왼쪽으로 양수 인덱스는 오른쪽으로 탐색을 진행하며 정렬 할 수 있도록 구현해 보았습니다.

 입력된 배열의 원소가 음수로만 구성되어 있을 때를 대비해여 예외처리 하는 것을 깜빡해서 bool 변수 bOnlyNegative를 활용하여 예외처리 해놓았습니다.

 다음 Explore은 Linked list로 진행하도록 하겠습니다. 피드백은 언제나 환영입니다! 감사합니다. 좋은 하루 되세요!