[백준/BOJ] 2473번: 세 용액

문제

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

2473번: 세 용액

해설

두 용액 문제를 응용하여 해결할 수 있는 문제이다.

두 포인터 알고리즘을 사용하는 문제인데, 두 포인터를 사용하면 두 개의 값만을 알 수 있다.

따라서 한개의 값을 더 정해야 하는데, 이는 고정적인 값을 하나 정한 후 두 포인터 알고리즘을 수행하는 것으로 해결하였다.

 

문제의 예시로 풀이를 해보자.

{-2, 4, -99, -1, 98}이 있다. 이를 정렬하면 {-99, -2, -1, 4, 98}이 된다.

이제 -99를 고정적인 값으로 두고, 두 포인터를 수행할 것이다.

low값을 -2, high 값을 98로 두고 low < high이 성립할 때가지 알고리즘을 수행한다.

-99 + -2 + 98 = -3으로 음수이므로 low의 값을 증가시켜준다. 만약 값이 양수라면 high을 감소시켜주면 된다.

이때마다 결과값이 절대값이 0에 더 가깝다면 세 개의 값을 저장해준다.

이 과정이 끝났다면 고정적인 값을 -2로 바꿔 low = -1, high = 98로 해준다.

즉, low = i + 1, high = n - 1이 된다.

 

모든 수행이 끝났다면 마지막에 저장되있는 세 개의 값이 정답이 된다.

코드

import java.util.*
import kotlin.math.abs

private lateinit var liquid: LongArray

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    liquid = LongArray(n)

    val st = StringTokenizer(readLine())
    repeat(n) { i -> liquid[i] = st.nextToken().toLong() }

    liquid.sort()

    val ans = selectLiquid(n)

    for(i in ans) print("$i ")
}

private fun selectLiquid(n: Int): LongArray {
    var standard = Long.MAX_VALUE
    val ans = LongArray(3)

    for(i in 0 until n -2) {
        var low = i + 1
        var high = n - 1

        while(low < high) {
            val mixLiquid = liquid[i] + liquid[low] + liquid[high]

            if(standard > abs(mixLiquid)) {
                standard = abs(mixLiquid)
                ans[0] = liquid[i]
                ans[1] = liquid[low]
                ans[2] = liquid[high]
            }

            if(mixLiquid < 0) low++
            else high--
        }
    }

    return ans
}