[알고리즘] 다중 포인터 패턴(Multiple Pointers -java)

[알고리즘 기초] 다중 포인터 패턴(Multiple Pointers -java)

JavaScript (JS) Algorithms and Data Structures Masterclass | Udemy
해당 포스팅은 JavaScript 알고리즘 & 자료구조 마스터클래스강의를 참고하여 작성했습니다.

 

 

이 패턴의 개념은 인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝 지점이나 양쪽 지점을 향해 이동시키는 것 입니다.
쉽게 이야기하면 이중 연결 리스트나 단일 연결 리스트를 만드는 것 입니다.(한쌍의 값이나 조건을 충족시키는 무언가를 찾는 개념)

다중 포인터 패턴(Multiple Pointers)

다음과 같이 오름차순으로 정렬된 배열에서 합계가 0인 첫 번째 쌍을 찾는 함수를 작성하세요.

예시
[-3, -2, -1, 0, 1, 2, 3] -> [-3, 3]
[-2, 0, 1, 3] -> X
[1, 2, 3] -> X

simpleSumZero

먼저 시간복잡도 O(N^2), 공간 복잡도 O(1)가 사용된 간단한 알고리즘입니다.

// O(N^2)
void simpleSumZero(List<Integer> arr) {
    for(int i = 0; i < arr.size(); i++) {
        for(int j = i+1; j < arr.size(); j++) {
            if(arr.get(i) + arr.get(j) == 0) {
                log.info("[{}, {}]", arr.get(i), arr.get(j));
                return;
            }
        }
    }
}

가능한 중첩 loop를 사용하는것은 좋지 않습니다.

순차적으로 탐색을 진행합니다.

j를 증가시키면서 i의 값과 연산을 합니다.

j가 끝에 도달하면 i를 증가시키고 j는 i의 값에서 +1을 합니다.

sumZero

시간 복잡도가 O(N)으로 리팩토링된 알고리즘 입니다.
sum의 조건에 따라서 탐색방향을 변경 합니다.

void sumZero(List<Integer> arr) {
    int left = 0;
    int right = arr.size() - 1; // 배열의 마지막 위치
    while (left < right) {
        int sum = arr.get(left) + arr.get(right);
        if(sum == 0) {
            log.info("[{}, {}]", arr.get(left), arr.get(right));
               return;
        } else if(sum > 0) {
            //sum > 0 이면 arr.get(right)가 더 크다는 의미
            //현재 arr는 오름차순으로 정렬되었기 때문
            right--;
        } else {
            left++;
        }
    }
}

하나의 loop를 사용하고 sum 조건에 의해서 탐색 방향을 변경 합니다.

TEST

@Slf4j
public class MultiplePointers {
    @Test
    void test() {
        simpleSumZero(List.of(-3, -2, -1, 0, 1, 2, 3));
        sumZero(List.of(-3, -2, -1, 0, 1, 2, 4));
    }
}

도전 과제

앞에서 배운 다중 포인터 패턴을 이용하여 고유값을 세는 함수를 작성해봅시다.

예시
[1, 1, 1, 2] -> 2
[1, 2, 2, 4, 4, 4, 5, 6] -> 5
[] -> 0
[-1, 0, 0, 1] -> 3

countUniqueValues

@Slf4j
public class CountUniqueValues {

    @Test
    void test() {
        Assertions.assertThat(countUniqueValues(new int[]{1, 1, 1, 2})).isEqualTo(2);
        Assertions.assertThat(countUniqueValues(new int[]{1, 2, 2, 4, 4, 4, 5, 6})).isEqualTo(5);
        Assertions.assertThat(countUniqueValues(new int[]{})).isEqualTo(0);
        Assertions.assertThat(countUniqueValues(new int[]{-1, 0, 0, 1})).isEqualTo(3);
    }

    int countUniqueValues(int[] arr) {
        int i = 0;
        for(int j = 1; j < arr.length; j++) {
            if(arr[i] != arr[j]) {
                i++;
                arr[i] = arr[j];
            }
        }

        if(arr.length == 0) return 0;

        return i+1;
    }
}

아래 그림과 같이 탐색을 합니다.

추가로 HashSet을 사용하여 간편하게 코드를 작성할 수도 있습니다.

int countUniqueValuesBySet(int[] arr) {
    Set<Integer> set = new HashSet<>();
    // O(N)
    for(int i = 0; i < arr.length; i++) {
        set.add(arr[i]); // O(1)
    }

    return set.size();
}

정리

• 각 배열의 index를 분리한다.
• 조건에 맞게 index를 조정하여 탐색 방향을 변경 한다.

#Study/java/algorithm