[알고리즘] 투포인터(Kotlin)

투 포인터 알고리즘이란

• 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘이다.

사용 예제

1. 특정한 합을 가지는 부분 연속 수열 찾기

• 부분 연속 수열의 시작점(start)과 끝점(end)의 위치를 기록
• 특정한 부분합을 M이라 가정할 때 알고리즘은 아래와 같다.

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
2. 현재 부분합이 M과 같다면 카운트한다.
3. 현재 부분합이 M보다 작으면 끝점(end)를 1 증가시킨다.
4. 현재 부분합이 M보다 크거나 같으면 시작점(start)을 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2번부터 4번 과정을 반복한다.

fun getTwoPointerCount(sum: Int) {
    val data = arrayOf(1, 2, 3, 2, 5, 8, 1, 9, 2, 3, 5)

    val size = data.size - 1
    var count = 0
    var intervalSum = 0
    var end = 0

    for (start in 0..size) {
        while (end <= size && intervalSum < sum) {
            intervalSum += data[end]
            end += 1
        }
        if (intervalSum == sum) count += 1

        intervalSum -= data[start]
    }

    println(count)
}

 

2. 정렬되어있는 두 리스트의 합집합

1. 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 한다.
2. 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리키도록 한다.
3. A[i]와 b[j] 중에서 더 작은 원소를 결과 리스트에 담는다.
4. 리스트 A와 B에서 더 이상 처리할 원소가 없을 때까지 2 ~ 4번의 과정을 반복한다.

fun getMergeArray(arr1: Array<Int>, arr2: Array<Int>): List<Int> {
    val answer = mutableListOf<Int>()

    var i = 0
    var j = 0

    while (i < arr1.size || j < arr2.size) {
        // arr2 배열이 모두 처리되었거나, arr1 배열의 원소가 더 작을 때.
        if (j >= arr2.size || (i < arr1.size && arr1[i] <= arr2[j])) {
            answer.add(arr1[i])
            i += 1
        } else {
            answer.add(arr2[j])
            j += 1
        }
    }
    return answer.toList()
}