백준 2467번: 용액

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

문제 풀이

투 포인터

sum = 두 용액의 특성값의 합

배열의 양쪽 끝에서부터 특성값의 합을 확인하고 0을 넘으면 right 감소, 아니면 left 증가

특성값의 합의 절댓값이 최솟값인 쌍을 찾아서 출력

풀이 설명

임의의 두 용액을 혼합하여 특성값이 가장 0에 가까워지는 두 용액을 찾아야 하고, 특성값이 음의 정수와 양의 정수로 나타나기 때문에 특성값의 합도 음의 정수 또는 양의 정수가 된다. 이때 두 용액의 특성값의 합이 음의 정수라면 용액을 교체해 특성값을 0에 가깝게 만드려면 현재 확인하는 두 용액 중 특성값이 더 작은 용액을 특성값이 조금 더 큰 용액으로 교체해야 한다.

반대로 특성값의 합이 양의 정수라면 두 용액 중 특성값이 더 큰 용액을 특성값이 조금 더 작은 용액으로 교체해야 0에 가까워질 수 있다. 그러므로 배열이 특성값을 기준으로 오름차순으로 정렬되어 있기 때문에 더 작은 용액은 인덱스가 더 작은 용액이고, 더 큰 용액은 인덱스가 더 큰 용액이다. 따라서 두 용액의 인덱스가 있다면 이 인덱스 만으로 더 큰 용액이나 더 작은 용액을 고를 수 있다는 뜻이다.

따라서 이에 따라 조합을 찾기 위해 left를 가장 특성값이 작은 용액의 인덱스 0으로 시작하고, right를 가장 특성값이 큰 용액의 인덱스 N - 1로 시작해 두 용액의 합을 확인하며 0보다 크다면 더 작은 용액을 확인하기 위해 right 값을 감소시키고, 0보다 작다면 더 큰 용액을 확인하기 위해 left 값을 증가시킨다.

이 과정에서 두 용액의 합이 0에 가깝다는 뜻은 두 용액의 합의 절댓값의 최솟값을 찾으면 된다는 것이므로 합의 절댓값이 최솟값이 되는 두 쌍을 찾아 저장하고 출력하면 된다.

소스 코드

import java.util.StringTokenizer
import kotlin.math.abs

fun main(){
    val N = readLine()!!.toInt()
    var left = 0
    var right = N - 1
    val arr = IntArray(N)
    val st = StringTokenizer(readLine())
    for(i in 0 until N){
        arr[i] = st.nextToken().toInt()
    }
    var min = Int.MAX_VALUE
    var sum = 0
    val answer = IntArray(2)
    while(left < right){
        sum = arr[left] + arr[right]
        if(min > abs(sum)){
            min = abs(sum)
            answer[0] = left
            answer[1] = right
        }
        if(sum > 0){
            right--
        } else {
            left++
        }
    }
    println("${arr[answer[0]]} ${arr[answer[1]]}")
}