투포인터(two pointer)

배열/리스트에 쌍을 검색하는 데 있어 이중 반복문을 사용하는 것 대신에 2개의 index를 저장하는 변수(두개의 포인터를)이용하여 효율적으로 검색을 하는 것. 이때, 배열이 정렬 및 특정한 규칙을 가진 경우가 많다. 즉, 연산이 이중 반복문으로 너무 오래걸리면서 특정한 조건의 쌍의 원소를 찾는 문제라면 투 포인터를 사용하는것을 고민해 봐야 한다.

가장 중요한건 두 쌍이 만족하는 조건을 잘 이해하고 언제 각각의 포인터를 움직여 줄것인가를 파악해야된다.

 

연속된 수열의 부분합

https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=java

프로그래머스

 

5 ≤  sequence. size  ≤ 1_000_000

1 ≤ sequence의 원소 ≤ 1_000

 

최대 100만개의 원소

 

일단, 두개의 index 사이의 합이 k가 되는 찾고 그중에서 가장 짧은 것.

 

여기서 핵심은 모든 원소는 양수라는 것 --> 합을 구하는데 있어 1개라도 추가되면 값이 상승한다.

 

문제의 2번째 예시를 보자

k = 5 [1, 1, 1, 2, 3, 4, 5]

 

범위를 나타내기 위해서 2개의 Index를 이용한다 

 

초기상태

빨간색 index = p1

파란색 index = p2

 

두 index가 구간 사이의 합이 1이라서 k보다 작으니까 합을 증가 시키기 위해 p2를 증가시킨다. 

모든 원소가 양수이기 때문에 두 인덱스 사이의 숫자들의 합이 k랑 같아지거나 또는 커진다. 

k와 두 구간의 합이 같아졌다. ---> 인덱스 기록해 둠

더 p2 증가 시키면 이미 k보다 커지기 때문에  것이 아니라 p1을 증가시켜야 한다

이후 구간 사이의 합이 4이라서 k보다 작으니까 합을 증가 시키기 위해 p2를 증가

두 구간의 합이 k보다 커졌기 때문에 구간의 합을 줄이기 위해 p1을 이동시킨다.

 

즉, k보다 구간의 합이 작으면 p2가 움직이는 것이고, k보다 구간의 합이 크면 p1가 움직인다.

 

code

class Solution {
    fun solution(sequence: IntArray, k: Int): IntArray {
        var answer: IntArray = intArrayOf()

        val rangeList = mutableListOf<Pair<Int, Int>>()

        var p2 = 0
        var interSum = 0
        for (p1 in 0 until sequence.size) {
            while (k > interSum && p2 < sequence.size) {
                interSum += sequence[p2]
                p2 += 1
            }
            // 구간의 합이 k보다 작거나 같다.
            if (interSum == k) {
                rangeList.add(p1 to p2 - 1)
            }
            // p1이 움직일 차례니까 기존의 p1은 빼주어야됨.
            interSum -= sequence[p1]
        }

        val comp = compareBy<Pair<Int, Int>> { it.second - it.first }.thenBy { it.first }
        rangeList.sortWith(comp)

        answer = intArrayOf(rangeList.first().first, rangeList.first().second)
        return answer
    }
}

 

용액

https://www.acmicpc.net/problem/2467

2467번: 용액

문제 분석.

 

2 <= N <= 100_000 -> 이중 반복문을 사용해서는 안된다. 

 

"정렬된 순서로 주어졌을 때", 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

 

정렬이 되어있음

index 0이 가장 작고 마지막 Index가 가장 크다.

 

두 수의 합이 얼마 0에 가깝나??? ---> 절대값이 얼마나 작은가?

 

절대값을 줄이려면,

이전의 합이 0을 기준으로

크다면 오른쪽 Index를 움직여서 합을 줄임

작다면 왼쪽 index를 움직여서 합을 키움

 

import kotlin.math.abs

var n = 0
lateinit var arr: IntArray

fun main() = with(System.`in`.bufferedReader()) {

    n = readLine().toInt()
    arr = readLine().split(" ").map { it.toInt() }.toIntArray()
    arr.sort()

    var leftIdx = 0
    var rightIdx = arr.size - 1
    var min = 2_000_000_000

    var answer = leftIdx to rightIdx
    while (leftIdx < rightIdx) {

        val temp = arr[leftIdx] + arr[rightIdx]
		// 최소값을 갱신한다
        if (abs(temp) <= min) {
            answer = arr[leftIdx] to arr[rightIdx]
            min = abs(temp)
        }
        // 두 용액의 합이 0보다 작으면 작은쪽 idx -->
        // 두 용액의 합이 0보다 크면 큰쪽  <-- idx
        if (temp <= 0) {
            leftIdx += 1
        } else {
            rightIdx -= 1
        }
    }

    println("${answer.first} ${answer.second}")
}