정렬된 정수 배열이 주어졌을 때, 각 요소의 제곱값을 구한 뒤 다시 오름차순으로 정렬된 배열을 출력하는 것이 이 문제의 목표입니다.
입력 및 출력 예시
예시 1
arr[ ] = { -3, -1, 0, 1, 4, 6 };출력:
{0, 1, 1, 9, 16, 36}설명: 주어진 배열 [-3, -1, 0, 1, 4, 6]의 각 요소를 제곱하면 [9, 1, 0, 1, 16, 36]이 되고, 이를 정렬하면 [0, 1, 1, 9, 16, 36]이 됩니다. 음수의 제곱은 양수가 되기 때문에 원래 배열이 정렬되어 있어도 제곱 후에는 재정렬이 필요합니다.
예시 2
arr[ ] = { 0, 1, 2, 8, 9 }출력:
{0, 1, 4, 64, 81}설명: 배열 [0, 1, 2, 8, 9]의 모든 요소가 양수 또는 0이므로, 제곱한 결과 [0, 1, 4, 64, 81] 역시 자동으로 정렬된 상태를 유지합니다.
문제 해결 접근 방법
이 문제는 투 포인터(Two-Pointer) 기법을 활용해 효율적으로 해결할 수 있습니다. 투 포인터 기법에서는 왼쪽(left)과 오른쪽(right) 두 개의 포인터를 사용하며, left는 배열의 첫 번째 요소를, right는 마지막 요소를 가리키도록 초기화합니다.
배열이 이미 정렬되어 있기 때문에 가장 큰 제곱값은 배열의 양 끝에서 나옵니다. 따라서 양 끝의 값들을 제곱하여 서로 비교하고, 더 큰 값을 결과 벡터에 넣는 방식으로 진행하면 추가 정렬 없이 O(n) 시간 안에 정렬된 결과를 얻을 수 있습니다.
알고리즘 단계
오름차순으로 정렬된 정수 배열을 입력받습니다.
squareAndSort(int *arr, int n) 함수는 정수 배열과 그 크기를 입력받아 각 요소의 제곱값을 정렬된 형태로 반환합니다.
left 포인터는 배열의 첫 번째 요소, right 포인터는 마지막 요소로 초기화합니다.
left와 right 위치 값의 제곱을 각각 계산한 뒤 서로 비교합니다.
더 큰 제곱값을 결과에 저장하고, 해당 포인터를 안쪽으로 이동시킵니다(left는 증가, right는 감소).
두 포인터가 교차할 때까지 위 과정을 반복합니다. 큰 값부터 채워지므로 최종적으로 결과를 뒤집어주면 오름차순 정렬이 완성됩니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
vector<int> squareAndSort(vector<int>&arr){
int left = 0;
int right = arr.size() - 1;
vector<int> vec;
while(left <= right){
int v1 = arr[left] * arr[left];
int v2 = arr[right] * arr[right];
if(v1 <= v2) {
vec.push_back(v2);
right--;
}
else {
vec.push_back(v1);
left++;
}
}
reverse(vec.begin(), vec.end());
return vec;
}
int main(){
vector<int> arr = {-3, -1, 0, 1, 4, 6};
vector<int> ans = squareAndSort(arr);
for(auto x : ans){
cout << x << " ";
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
0 1 1 9 16 36
배열의 각 요소를 제곱하면 9, 1, 0, 1, 16, 36이 되며, 투 포인터 알고리즘이 큰 값부터 차례대로 저장하기 때문에 reverse 함수로 한 번 뒤집어 주면 최종적으로 0 1 1 9 16 36이라는 정렬된 결과를 얻을 수 있습니다.
이 방식의 시간 복잡도는 O(n)으로, 단순히 전체를 제곱한 뒤 정렬하는 O(n log n) 방식보다 효율적입니다. 공간 복잡도는 결과를 저장하기 위한 O(n)입니다.