[Algorithm] Sorted squared array 반환하기

  오늘은 보다 간단한 문제에 대해서 알아보자.  Ascending order 로 정렬된 input array 가 주어졌을 때, Sorted Sqaured output array 를 반환하라는 문제 상황이다. 예를 들어 [1,2,3,4,5] 가 주어지면 [1,4,9,16,25] 를 반환한다. 가장 쉽게 떠오르는 것은 그냥 input array 를 순회하며 squared value 를 원소로 가지는 배열을 만든 다음 sorting 해서 반환해주는 방법이다. 이렇게 구현한 경우에는 시간 복잡도는 O(NlogN) 이고 공간 복잡도는 O(N) 이다.

#include <vector>
using namespace std;
// time :  O(NlogN)
// space : O(N)
vector<int> sortedSquaredArray(vector<int> array) {
  // Write your code here.
  vector<int> ans;
  for(auto ele : array){
    ans.push_back(ele*ele);
  }
  sort(ans.begin(), ans.end());
  return ans;
}

  만약, 면접관 혹은 문제상황에서 보다 최적화된 풀이를 요구하면 어떻게 하면 될까? 가령, 이 문제를 O(N) 에 풀라고 한다면? 이를 위해서는 output 을 sorting 하는 과정없이, input array 를 순회하면서 output array 의 적절한 position 에 squared value 를 insert 해주면 된다.

 

  이를 위해서 array 의 가장 작은 원소의 인덱스를 의미하는 left  = 0 와 가장 큰 원소의 인덱스를 의미하는 right = array.size()-1 을 선언한 다음 array 를 순회하며 array[left] 와 array[right] 의 절댓값을 비교한 뒤 더 큰 원소의 제곱을 output array 의 끝부터 채워넣어주면 된다. 이렇게 구현하면 시간 복잡도는 O(N) 이고 공간 복잡도는 O(N) 으로 보다 최적화된 알고리즘이라고 할 수 있겠다.

#include <vector>
using namespace std;
// time :  O(N)
// space : O(N)
vector<int> sortedSquaredArray(vector<int> array) {
  // Write your code here.
  vector<int> ans(array.size());
  int right = array.size()-1; int left = 0;
  for(int i = array.size()-1; i >= 0 ; i--){
    if(abs(array[left]) > abs(array[right])){
      ans[i] = array[left]*array[left];
      left++;
    }
    else{
      ans[i] = array[right]*array[right];
      right--;
    }
  }
  return ans;
}

https://github.com/versatile0010/AlgoExpert