[Leetcode][Java] 투 포인터로 더욱 빠른 배열 연산을 수행해 보자(1)

투 포인터 알고리즘 :

배열을 효율적으로 탐색하기 위해, 동시에 두 개의 포인터를 사용하여 배열을 순회하는 알고리즘입니다.

별도의 정렬 알고리즘 없이 정렬된 배열을 얻을 수 있게 해 주거나,

이중반복문으로 처리해야 할 문제를 반복문 하나로 처리하거나,

추가적인 배열 생성 없이 그대로 배열을 수정하는(in-place modification) 등등,

시간/공간복잡도를 줄여주는 유용한 접근법입니다.

 

Leetcode에 등록된 실제 예제를 통해 투 포인터 알고리즘에 대해서 알아보겠습니다.

 

 

---

 

 

977.Squares of a Sorted Array

---

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

 

비내림차순으로 정렬된 배열이 제시됩니다. (모든 원소가 이전 인덱스의 원소보다 크거나 같음[≤].)
제시된 배열의 각 원소를 제곱하여, 다시 비내림차순으로 정렬한 다음, 그 배열을 반환하세요.

 

 

실행 예시 : 

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

 

 

 

일반적인 해답 :

import java.util.Arrays;

class Solution {
    public int[] sortedSquares(int[] nums) {
        
        for (int i=0; i<nums.length; i++){
            nums[i] = nums[i] * nums[i];
        }
        
        Arrays.sort(nums);
        
        return nums;
    }
}

가장 단순한 방법으로 접근해 보겠습니다.

맨 앞의 원소부터 차례대로, 각 원소의 값을 제곱한 다음( nums[i] = nums[i] * nums[i] ),

Java에 내장된 배열 정렬 기능인 Array.sort로 정렬합니다.

 

 

배열의 처음부터 끝까지 차례대로 제곱해 줍니다.

 

 

배열 [-4, -1, 0, 3, 10]을 마지막 원소까지 제곱한 결과는 [16, 1, 0, 3, 100]이 되었습니다.

제곱은 잘 되었지만, 부호가 음수였던 값들이 제곱이 되면서

배열의 크기 순서는 뒤죽박죽이 되어 버렸네요. 

따라서 배열을 다시 한 번 정렬해 주도록 합시다.

Java에 내장된 배열 정렬 기능인 Array.sort()를 사용하겠습니다.

 

Array.sort()를 이용해 배열을 정렬해 줍니다.

 

참고 : Array.sort() 연산은 배열의 크기에 대해 O(nlogn)의 시간복잡도를 갖습니다.

https://javanitto.tistory.com/6

 

 

원하는 결과를 얻는 데 성공했고, 다음과 같은 실행 결과가 나타납니다.

[ 실행 결과 ] : 런타임 34ms, 메모리 사용량 55.5MB

 

 

 

 

 

그런데 문제의 아래쪽에 다음과 같은 조건이 제시됩니다.

 

 

Follow up: 

Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?
 

"모든 원소를 제곱한 다음 배열을 정렬하는 방법은 너무 간단하죠.
 다른 접근법을 이용해 시간복잡도 O(n)을 갖는 해답을 찾을 수 있을까요?"

 

 

---

 

 

 

투 포인터를 활용한 해답 :

솔루션 제공자 : wangzi6147, 2019.01.20

class Solution {
    public int[] sortedSquares(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        int i = 0, j = n - 1;
        for (int p = n - 1; p >= 0; p--) {
            if (Math.abs(arr[i]) > Math.abs(arr[j])) {
                result[p] = arr[i] * arr[i];
                i++;
            } else {
                result[p] = arr[j] * arr[j];
                j--;
            }
        }
        return result;
    }
}

 

이제 투 포인터를 활용한 해답을 살펴보겠습니다.

 

제시되는 배열은 이미 비내림차순으로 정렬이 되어 있기 때문에,

절댓값이 가장 큰 값(제곱을 했을 경우 가장 큰 값)은

배열의 시작 지점 또는 끝 지점에 존재할 것입니다.

 

여기에 착안해 봤을 때, 

시작 지점의 값과 끝 지점의 값부터 비교하여,

실제로 절댓값이 더 큰 값부터 제곱하여 역순으로 배열에 저장하면,

자연히 정렬된 배열을 얻을 수 있을 것입니다.

 

 

 

그러기 위해서 두 개의 정수형 변수를 선언하여,

한 배열 내부에 존재하는 서로 다른 두 개의 지점을 나타내게 하도록 하겠습니다.

 

int n = arr.length;
int i = 0, j = n - 1;

- 포인터 1 : 배열의 시작점을 가리키는 정수형 변수 i를 선언합니다.

- 포인터 2 : 배열의 끝점을 가리키는 정수형 변수 j를 선언합니다.

 

 

int n = arr.length;
int[] result = new int[n];
for (int p = n - 1; p >= 0; p--) {
	...
}

또한 정답으로 제출할 배열을 추가로 생성하도록 하겠습니다.

result라는 이름으로 비어있는 배열을 하나 생성하고,

배열의 끝부분(int p)부터 알고리즘을 실행하도록 하겠습니다.

 

원본 배열 arr에 두 개의 포인터 i, j를 놓습니다. 정답으로 제출할 배열 result의 끝 지점부터 알고리즘을 시작합니다.

 

 

 

if (Math.abs(arr[i]) > Math.abs(arr[j])) {
    result[p] = arr[i] * arr[i];
    i++;
} else {
    result[p] = arr[j] * arr[j];
    j--;
}

실행할 알고리즘은 다음과 같습니다.

- i와 j가 가리키는 두 값의 절댓값을 비교합니다.

- i의 절댓값이 더 크다면, i를 제곱하여 result 배열의 현재 지점에 저장합니다.

  그 후, i를 한 칸 뒤로 이동합니다.

- j의 절댓값이 더 크다면, j를 제곱하여 result 배열의 현재 지점에 저장합니다.

  그 후, j를 한 칸 앞으로 이동합니다.

 

 

1회차 :

arr[i]의 절댓값은 4, arr[j]의 절댓값은 10입니다.

arr[j]의 절댓값이 더 크므로, j의 값을 제곱해서 result의 현재 지점에 넣겠습니다.

 

 

 

2회차 :

앞서 arr[j]의 절댓값이 더 컸기 때문에 j를 한 칸 앞으로 이동하였습니다.현재 

arr[i]의 절댓값은 4, arr[j]의 절댓값은 3입니다.

arr[i]의 절댓값이 더 크므로, i의 값을 제곱해서 result의 현재 지점에 넣겠습니다.

 

 

 

3회차 :

앞서 arr[i]의 절댓값이 더 컸기 때문에 i를 한 칸 뒤로 이동하였습니다.

다시 arr[i]의 절댓값과 arr[j]의 절댓값을 비교하여,

더 큰 값을 제곱해서 result의 현재 지점에 넣어주고,

더 큰 쪽의 포인터를 이동해 줍니다.

 

 

위와 같은 과정을 반복하여, result의 0번째 인덱스까지 값을 넣은 다음 반복문은 종료됩니다.

실행 결과, result에는 제곱한 값들이 큰 값부터 차례대로 저장되었습니다.

 

 

 

[ 실행 결과 ] : 런타임 1ms, 메모리 사용량 44.2MB

 

투 포인터를 활용하여, 

반복문의 각 회차마다 가장 큰 결과부터 배열의 끝에 저장하는 알고리즘을 구상하였습니다.

그 결과  Array.sort()와 같이 O(n) 이상의 시간복잡도를 가진 정렬 메서드를 추가해 줄 필요가 없이,

O(n)의 시간복잡도만으로 원하는 결과를 얻어낼 수 있었으며, 

그 결과 실행 시간을 1ms로 단축시킬 수 있었습니다.

 

---

 

 

이상으로 Leetcode의 977번 문제를 투 포인터로 빠르게 푸는 방법을 알아보았습니다.

이어지는 포스팅에서 배열 문제를 투 포인터로 해결하는 또다른 예시를 알아보도록 하겠습니다.