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

https://atomicliquors.tistory.com/8

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

 

지난 시간에 이어서, Leetcode에 등록된 배열 문제의 투 포인터 알고리즘 솔루션을 알아보겠습니다.

 

 

---

 

167. Two Sum II - Input Array Is Sorted

---

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

 

인덱스가 1부터 시작하고, 비내림차순으로 정렬된 정수 배열 numbers가 제시됩니다.
서로 합한 값이 특정 숫자와 같은 두 개의 숫자를 찾으세요.
두 개의 숫자는 numbers[인덱스1]과 numbers[인덱스2]라 하고,
이 때 1 <= 인덱스 1, 2 <= numbers.length입니다.

두 숫자의 인덱스인 인덱스1과 인덱스2를,
길이 2인 정수 배열 [index1, index2]와 같이 하나로 합쳐서 반환하세요.
모든 문제는 하나의 정답만 존재하도록 생성됩니다. 같은 원소를 두 번 사용할 수는 없습니다.
해답 코드가 사용하는 메모리 공간은 상수여야 합니다. [O(1)]

 

 

실행 예시 : 

입력: numbers = [2,7,11,15], target = 9
출력: [1,2]

해설: 합이 9에 해당하는 두 숫자는 첫 번째 숫자와 두 번째 숫자인 2와 7입니다. 따라서, 배열 [1, 2]를 반환합니다.

 

 

 

 

해답 :

솔루션 제공자 : titanduan3, 2018.10.13

class Solution{
	public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        if (numbers == null || numbers.length < 2) return result;
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                result[0] = i + 1;
                result[1] = j + 1;
                break;
            } else if (sum > target) {
                j--;
            } else {
                i ++;
            }
        }
        return result;
    }
}

 

 

int[] result = new int[2];
if (numbers == null || numbers.length < 2) return result;

정답을 담을 배열 result를 선언합니다.

numbers 배열이 비어 있거나 길이가 2보다 작아서 정답을 구할 수 없는 경우, 빈 배열을 반환합니다.

 

int i = 0, j = numbers.length - 1;
        while (i < j) {
            
        }

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

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

 

지난 시간처럼 시작 지점의 값과 끝 지점의 값부터 출발하겠습니다.

지난 문제와 마찬가지로 배열이 비내림차순으로 정렬되어있습니다.

배열의 왼쪽으로 갈수록 원소는 작아지고, 오른쪽으로 갈수록 원소는 커집니다.

이 성질을 이용해 보도록 하겠습니다.

 

 

if (sum == target) {
    result[0] = i + 1;
    result[1] = j + 1;
    break;
}

두 수를 합했을 때 원하는 값이 나왔다면 

result 배열에 두 수의 인덱스 값을 각각 저장해 주면 됩니다.

정답에 해당하는 인덱스는 1부터 세기로 했기 때문에, 

각 인덱스에 1을 더해 줍니다.

 

 

...
} else if (sum > target) {
    j--;
} else {
    i++;
}

하지만 두 수의 합이 원하는 값과 다르다면,

더한 값이 원하는 값보다 작을 경우 왼쪽 포인터를 중앙 쪽으로 한 칸 이동해 보고,
(더 큰 원소를 더하면 합도 더 커지겠죠.)

반대로 원하는 값보다 클 경우 오른쪽 포인터를 중앙 쪽으로 이동하겠습니다.

(마찬가지로 더 작은 원소를 더하면 합도 더 작아집니다.)

 

구하고자 하는 합이 18이라고 합시다. 

가장 먼저 포인터가 놓인 양 끝값을 합해 보면 합은 17입니다.

18보다 작은 값이네요. 합이 더 커지도록 왼쪽의 i값을 이동해 보겠습니다.

 

이번에는 22가 나왔습니다. 

18보다 큰 값이기 때문에, 합이 더 작아지도록 오른쪽의 j값을 이동해 보겠습니다.

 

이제 원하는 합인 18이 나왔습니다.

7, 11은 1부터 세면 각각 2번째, 3번째 인덱스에 있기 때문에

배열 [2,3]을 정답으로 반환하게 됩니다.

 

 

 

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

 

---

 

 

1089. Duplicate Zeros

---

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

 

길이가 고정된 배열 arr이 제시됩니다. 0이 나올 때마다 원소를 복사하고, 나머지 원소를 오른쪽으로 이동하세요.
배열의 길이를 넘어선 원소들은 저장하지 않습니다. 입력된 배열 내에(in-place) 수정사항을 적용하도록 하며, 반환값은 반환하지 않습니다.

 

실행 예시 : 

입력: arr = [1,0,2,3,0,4,5,0]
출력: [1,0,0,2,3,0,0,4]

 

 

 

 

해답 :

솔루션 제공자 : lee215 /w davidluoyes, 2019.07.10

 

class Solution{
    

public void duplicateZeros(int[] arr) {
        int countZero = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) countZero++;
        }
        int len = arr.length + countZero;

        for (int i = arr.length - 1, j = len - 1; i < j; i--, j--) {
            if (arr[i] != 0) {
                if (j < arr.length) arr[j] = arr[i];
            } else {
                if (j < arr.length) arr[j] = arr[i];
                j--;
                if (j < arr.length) arr[j] = arr[i]; 
            }
        }
    }
    
}

 

 

int countZero = 0;
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == 0) countZero++;
}

가장 먼저 0의 갯수를 세어줍니다. 

정수형 변수 countZero를 선언하고,

배열 전체를 돌며 0의 갯수를 세어서 countZero에 저장해 줍니다.

 

 

int len = arr.length + countZero;

for (int i = arr.length - 1, j = len - 1; i < j; i--, j--) {
    ...
}

이번에는 배열의 길이를 초과하는 지점에 포인터를 놓아봅시다.

- 포인터 1 : 정수형 변수 i를 선언하여, arr의 끝 지점에 놓습니다.

- 포인터 2 :  정수형 변수 j를 선언하여, arr의 끝으로부터 countZero만큼 떨어진 지점에 놓습니다.

 

 

 

 

 

if (arr[i] != 0) {
    if (j < arr.length) 
   	arr[j] = arr[i];
} else {
    if (j < arr.length) 
    	arr[j] = arr[i];
    j--;
    if (j < arr.length) 
    	arr[j] = arr[i]; 
}

반복문의 반복 회차마다 두 가지 조건을 판단하게 될 것입니다.

- arr[i]가 0인가?

- 포인터 j가 배열 내로 들어왔는가?

 

 

1. arr[i]가 0이 아니다 :

 포인터 j가 배열 내로 들어왔다면, j 위치의 값을 i 위치의 값으로 바꿉니다.

 

2. arr[i]가 0이 맞다 :

 a. 포인터 j가 배열 내로 들어왔다면, j 위치의 값을 i 위치의 값으로 바꿉니다.

 b. j를 한 칸 왼쪽으로 옮깁니다.

 c. 다시,  포인터 j가 배열 내로 들어왔을 경우, j 위치의 값을 i 위치의 값으로 바꿉니다.

 

반복문이 끝나면 i, j 모두 한 칸씩 왼쪽으로 이동합니다.

 

 

 

2-b :

i가 가리키는 값은 0이고, j는 아직 배열 바깥의 위치를 가리키고 있습니다.

j를 한 칸 왼쪽으로 옮기는 연산만 수행합니다.

 

 

1:

i가 0이 아닌 4를 가리키고 있으며, j가 배열 내로 들어왔습니다.

j 위치의 값을 i 위치와 같은 4로 변경하겠습니다.

 

 

 

2-a, 2-b, 2-c:

i가 0을 가리키고 있으며, j도 배열 안으로 들어왔습니다.

문제에서 요구하는 대로 0을 복사해 줘야 합니다.

 

따라서 

2-a. j위치의 값을 i 위치에 존재하는 0으로 바꾸고,

2-b : j를 한 칸 앞으로 옮긴 다음,

2-c. 한 칸 옮겨간 j위치의 값을 다시 i 위치에 존재하는 0으로 바꿔줍니다.

 

 

 

i와 j가 마주치며 반복문은 종료되고, 

문제에서 요구하는 대로 배열 내에 존재하는 0이 모두 한번씩 복사되었습니다.

 

 

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

 

 

---

 

 

 

941. Valid Mountain Array

---

Given an array of integers arr, return true if and only if it is a valid mountain array.

Recall that arr is a mountain array if and only if:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

 

정수형 배열 arr이 제시됩니다. arr이 Mountain Array에 해당할 경우에만 true를 반환하세요.
다음 조건을 만족할 때에만 arr을 Mountain Array로 간주합니다.

• 배열의 길이가 3 이상.
• 0 < i < arr.length - 1 인 i에 대해 다음과 같은 일정 구간이 존재함.
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

배열과 증가추세, 감소추세가 삼각형 모양을 이룰 때만 Mountain Array로 취급합니다.

 

 

 

해답 :

솔루션 제공자 : hi-malik, 2022.01.25

class Solution {
    public boolean validMountainArray(int[] arr) {
        if(arr.length < 3) return false;
        int i = 0;
        int j = arr.length - 1;
        while(i + 1 < arr.length - 1 && arr[i] < arr[i + 1]) i++;
        while(j - 1 > 0 && arr[j] < arr[j - 1]) j--;
        return i == j;
    }
}

 

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

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

- 포인터 2 :

배열의 끝점을

가리키는 정수형 변수 j를 선언합니다.

 

 

 

 

 

while(i + 1 < arr.length - 1 && arr[i] < arr[i + 1]) i++;

첫 번째 while문을 수행합니다.

i를 시작지점으로부터 계속 전진시키겠습니다.

i가 배열의 끝에 닿거나,

i 다음 위치의 값이 현재 위치보다 크지 않다면 while문이 종료됩니다.

 

 

while(j - 1 > 0 && arr[j] < arr[j - 1]) j--;

두 번째 while문을 수행합니다.

j를 끝 지점으로부터 계속 당겨오겠습니다.

j가 배열의 맨 앞에 닿거나,

j 다음 위치의 값이 현재 위치보다 크지 않다면 while문이 종료됩니다.

 

 

 

모든 while문이 종료되었을 때 두 포인터가 서로 마주치고 있다면, 

이 배열을 Mountain Array로 판단하여 true를 반환합니다.

 

 

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

 

 

 

---

 

 

 

이상으로 Leetcode에 등록된 배열 문제들을 투 포인터로 해결하는 솔루션들을 알아보았습니다.

기본적인 반복문 개념을 익힌 코더들이라면,

위와 같은 문제들을 마주쳤을 때

인덱스 i를 일방적으로 증가시키는 for문 또는 while문,

또는 그 내부에 인덱스 j를 활용한 반복문을 넣은 중첩 루프를 떠올릴 수 있을 것입니다.

 

하지만 문제의 난이도가 오르면 도저히 해결 방법이 떠오르지 않거나,

반복된 중첩 루프 사용으로 지나치게 시간이 오래 걸리는 답안을 제출하게 될 수도 있습니다.

이 때 투 포인터 기법의 도움을 받으면 막막했던 문제를 해결하거나,

연산 시간을 대폭 감축한 새로운 문제해결 방법을 발견할 수 있습니다.

 

하나가 아닌 두 개의 시점을 제시하는 투 포인터 기법을 이용해

더욱 창의적이고 효과적인 해결방법을 떠올려 보시길 바랍니다.