Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 변환된 배열 정렬하기 – 투 포인터 알고리즘 풀이

문제 소개

정수로 이루어진 정렬된 배열 nums와 세 개의 정수 a, b, c가 주어졌다고 가정해 보겠습니다. 우리가 해야 할 일은 배열의 각 원소 x에 이차함수 f(x) = ax² + bx + c를 적용한 후, 결과 배열을 다시 오름차순으로 정렬된 상태로 만드는 것입니다.

예를 들어 입력이 nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5라면 각 원소에 함수를 적용한 결과는 [3, 9, 15, 33]이 되며, 이것이 곧 정답이 됩니다.

접근 방법: 투 포인터(Two Pointers)

모든 원소에 함수를 적용한 뒤 일반적인 정렬을 수행하면 O(n log n)의 시간이 걸립니다. 하지만 입력 배열이 이미 정렬되어 있다는 조건을 활용하면 O(n) 만에 문제를 해결할 수 있습니다.

핵심은 이차함수의 그래프, 즉 포물선의 성질에 있습니다.

  • a ≥ 0인 경우: 포물선이 위로 열려 있으므로 함수 값의 최댓값은 항상 배열의 양쪽 끝에서 발생합니다.
  • a < 0인 경우: 포물선이 아래로 열려 있으므로 함수 값의 최솟값 역시 배열의 양쪽 끝에서 발생합니다.

따라서 두 개의 포인터(start, end)를 배열의 양 끝에 배치하고, 매 단계마다 양 끝 값 중 더 적합한 쪽을 결과 배열의 뒤쪽(a ≥ 0) 또는 앞쪽(a < 0)부터 차례대로 채워 나가면 됩니다.

알고리즘 단계

  1. x, a, b, c를 인자로 받아 ax² + bx + c를 반환하는 함수 f()를 정의합니다.
  2. n을 nums의 크기로 설정하고, start = 0, end = n - 1로 초기화한 뒤 크기 n의 결과 배열 ret을 준비합니다.
  3. a ≥ 0인 경우: i를 n - 1부터 0까지 감소시키면서 다음을 반복합니다.
    • x = f(nums[start], a, b, c), y = f(nums[end], a, b, c)를 계산합니다.
    • x > y이면 start를 1 증가시키고 ret[i] = x를 저장합니다.
    • 그렇지 않으면 ret[i] = y를 저장하고 end를 1 감소시킵니다.
  4. a < 0인 경우: i를 0부터 n - 1까지 증가시키면서 같은 방식으로 진행하되, 더 작은 값을 결과 배열의 앞쪽부터 채웁니다.
  5. 최종적으로 ret을 반환합니다.

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   int f(int x, int a, int b, int c){
      return a * x * x + b * x + c;
   }
   vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
      int n = nums.size();
      int start = 0;
      int end = n - 1;
      vector<int> ret(n);
      if (a >= 0) {
         for (int i = n - 1; i >= 0; i--) {
            int x = f(nums[start], a, b, c);
            int y = f(nums[end], a, b, c);
            if (x > y) {
               start++;
               ret[i] = x;
            }
            else {
               ret[i] = y;
               end--;
            }
         }
      }
      else {
         for (int i = 0; i < n; i++) {
            int x = f(nums[start], a, b, c);
            int y = f(nums[end], a, b, c);
            if (x < y) {
               start++;
               ret[i] = x;
            }
            else {
               ret[i] = y;
               end--;
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {-4,-2,2,4};
   print_vector(ob.sortTransformedArray(v, 1, 3, 5));
}

입력

{-4,-2,2,4}, 1, 3, 5

출력

[3, 9, 15, 33]

복잡도 분석

시간 복잡도: O(n) — 각 원소를 정확히 한 번씩만 처리하므로 선형 시간에 동작합니다.
공간 복잡도: O(n) — 변환된 결과를 저장할 배열이 필요합니다.