Two Pointers, 정렬된 제곱의 배열 구하기 (squares of a sorted array)

문제

오름차순으로 정렬된 음수가 포함된 숫자 배열이 있다. 이 배열의 제곱 결과를 오름차순으로 정렬된 배열 형태로 만들어 보아라.

ex) [-4,-1,0,3,10]가 입력으로 들어온다면, [16,1,0,9,100] 가 제곱한 결과가 되고 결과는 [0,1,9,16,100] 이 된다.

입력: [-4,-1,0,3,10]
출력: [0,1,9,16,100]

해법 1: 모두 제곱하고 정렬하기

말 그대로 제곱부터 먼저 구한 뒤에 모두 정렬하는 방법이다. 제곱할 때 N 의 복잡도가 들고, 정렬할 때 정렬 알고리즘에 의해 log N 의 복잡도가 나온다.

class Solution {
    public int[] sortedSquares(int[] A) {
        int N = A.length;
        int[] ans = new int[N];
        for (int i = 0; i < N; ++i)
            ans[i] = A[i] * A[i];

        Arrays.sort(ans);
        return ans;
    }
}

가장 간단한 해법이다.

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N) 혹은 O(log N)

파이썬은 Timesort 알고리즘을 사용하고, 자바는 퀵소트 알고리즘과 비슷한 알고리즘을 사용하여 정렬한다. 파이썬은 O(N) 자바는 O(log N) 의 시간복잡도가 걸린다.

해법 2: Two pointer

• 배열이 정렬되어 있다는 특성을 이용한다.
• 음의 최고값은 자연적으로 첫번째, 양의 최고값은 자연적으로 마지막에 온다.
• 0을 기준으로 음의 영역은 내림차순 정렬, 양의 영역은 오름차순 정렬로 볼 수도 있다.
• 음이든 양이든 숫자 자체가 크면 제곱의 값은 크게 나오므로, 가장 큰 값부터 순서대로 마지막에 넣으면 된다.

class Solution {
    public int[] sortedSquares(int[] n) {
        int l = 0;
        int r = n.length - 1;

        int ans[] = new int[n.length];
        int p = r;

        while(l<=r) {
            int al = Math.abs(n[l]);
            int ar = Math.abs(n[r]);

            if (l==r) {
                ans[p] = al * al;
                break;
            }

            if(al > ar) {
                ans[p--] = al * al;
                l++;
            } else {
                ans[p--] = ar * ar;
                r--;
            }
        }

        return ans;
    }
}

• 두 값을 비교한 결과가 새로운 배열에 들어가며 그 결과가 쌓여 정렬된 배열이 되는 것은 병합 정렬과 비슷하다.