(문제 해결 패턴) 멀티플 포인터 패턴

어레이 내 정렬된 엘리먼트와 관련된 문제를 해결할 때 멀티플 포인터 패턴이 해답을 줄 수 있다.

 

이게 무슨말인가?

글로써 보면 조금 어렵다.

 

---

 

문제 예시를 보자.

/*
Write a function called sumZero which accepts a sorted array of integers.
The function should find the first pair where the sum is 0.
Return an array that includes both values 
that sum to zero or undefined if a pair does not exist
*/

/*
해설:
정렬된 정수값을 가진 어레이를 인수로 받는 sumZero라는 함수를 작성해라.
함수는 어레이 내 정수의 합계가 0인 첫번째 쌍을 배열화하여 반환한다.
만약 어레이 내 정수의 합계의 쌍 중 0이 되는 수가 없다면 undefined를 반환한다.
*/

sumZero([-3, -2, -1, 0, 1, 2, 3]) // [-3, 3]
sumZero([-2, 0, 1, 3]) // undefined
sumZero([1, 2, 3]) // undefined

풀이 전 생각)

• 어레이 내 각 엘리먼트를 하나씩 골라서 순회하는 방법을 떠올릴 수 있다.
• sum이라는 변수를 만든 뒤, 어레이 내를 순회하며 비교할 엘리먼트 쌍을 합계해서 할당한다.
  만약 값이 0이라면 그 값 쌍을 어레이로 만들어 반환한다.
• 어레이 내 정수의 엘리먼트의 합계가 0이 될 수 없을 때, undefined를 출력한다.
  그러니 별도의 return은 만들지 않는다.

 

---

위와 같은 사고방식을 통해 O(N^2)의 방법으로 위의 문제를 다소 naive하게 해결할 수 있다.

결국, 어레이 내부의 엘리먼트를 각각 순회하며 모든 합계 값을 비교하면 되는 문제이기 때문이다.

 

아래 코드는 위의 문제를 O(N^2) 시간 복잡도로 해결한 것이다.

// naive example
function sumZero(arr) {
    for(let i = 0; i < arr.length; i++) {          // (1)
        for(let j = i + 1; j < arr.length; j++) {  // (2)
            if(arr[i] + arr[j] === 0) {            // (3)
                return [arr[i], arr[j]]            // (4)
            }
        }
    }
}

/*
(1) 일단 어레이의 첫번째 인덱스부터 탐색을 시작한다.
(2) 첫번째 for문의 엘리먼트를 기준으로 변수 j에 대한 어레이의 순환을 시작한다. (2중 for문)
(3) 두 값 쌍이 0이라면
(4) 0으로 만드는 값 쌍을 배열로 만들어 return 한다.

(5) 값 쌍이 0이 되는 것이 없을 경우, return을 하지 않으면 자동적으로 undefined가 된다.
*/

• for문 내부에 for문이 하나 더 있으므로 O(N^2)의 시간복잡도를 가진다.
• 어레이 내부를 모두 순환하며 연산하는 방식이다.
• 모든것들이 모두 순환되었을 때 return문이 존재하지 않으므로 undefined가 리턴된다.

---

 

이러한 문제는 멀티플 포인터 패턴을 이용한다면 O(N)으로 해결이 가능하다.

 

멀티플 포인터 패턴은 내부를 순환하는 포인터를 2개를 만들어

어레이를 효과적으로 탐색하는 방법이다.

 

한 배열에 하나의 인덱스(포인터)가 작동해서 순회하는게 아니라

아예 한 배열에 2개의 포인터가 한꺼번에 돌아가는 개념이다.

 

이때 포인터가 골라줄 위치는 문제마다 다르겠지만

통상적으로 0번째 인덱스와 마지막 인덱스를 찍어서 순회할 수 있다.

 

아래는 멀티플 포인터 패턴을 적용한 문제풀이이다.

function sumZero(arr) {
    let left = 0; // 왼쪽 포인터
    let right = arr.length - 1 // 오른쪽 포인터
    while(left < right) {                  // (1)
        let sum = arr[left] + arr[right]   // (2)
        
        if(sum === 0) return [arr[left], arr[right]] // (3)
        else if (sum > 0) right--                    // (4) 
        else left++                                  // (5)
    }
}

/*
(1) 멀티플 포인터가 순회를 할 때,
    서로의 위치를 크로스해서 순환할 필요는 없으므로 
    left가 right보다 크다면 반복문을 종료한다.
    
(2) 어레이 내 값을 더해서 sum 변수에 할당한다.

(3) sum이 0이라면 값을 리턴한다.

(4) 만약 더한 값이 양수라면 오른쪽 포인터의 값을 감소시킨다.
    [-3, -2, -1, 0, 1, 2, 5]가 인수로 전달될 경우,
    -3 + 5는 양수이다. 따라서 오른쪽 포인터가 줄어서 더 작은 값을 비교하게 해야한다.
    
(5) 만약 더한 값이 음수라면 왼쪽 포인터의 값을 증가시킨다.
    음수값이 너무 크다는 의미이기 때문이다.
    우리가 비교하는 어레이는 정렬된 어레이이므로
    left를 하나 증가시켜 비교하는 값의 기준을 다르게 해야한다.
*/

위와 같은 해결 방법을 통해 반복문을 하나(while)만 쓰고

문제를 해결할 수 있었다.

 

정렬된 어레이를 계산하기 위해서는

멀티플 포인터 패턴을 잘 활용하면 좋을 것 같다.

물론, 반복문의 탈출문을 어떻게 구상해야할지는 깊이 사고할 필요성이 있다.

 

 

새로 배운 메서드 / 키워드

• 없음