[백준] 25. 세 용액 2473 해설

세 용액

2473번: 세 용액

 

문제

 

풀이

해당 문제는 이전에 용액2467 문제를 풀었기 때문에 투 포인터를 이용한 문제라는 것을 알고 있었습니다.

하지만 선택해야 되는 용액이 3개이기 때문에 약간의 응용만 해주면 됩니다.

 

결국은 투 포인터를 이용해야 되지만 우리는 3개의 용액을 선택해야 됩니다. 따라서 하나의 용액은 결정되었다는 가정하에 2개의 용액만 투 포인터로 구해주면 됩니다. 

(투 포인터 + 완전탐색)

 

풀이 방법은 다음과 같습니다.

1. 용액을 정렬해 준다.
2. for 문을 돌면서 i번째 용액을 고정시켜 준다.
3. i+1번째 용액부터 마지막 용액까지 투 포인터를 진행시켜 i번째 용액을 더 했을 때 0에 가장 가까운 용액을 찾아준다.

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run{
    fun input(): Long {
        nextToken()
        return nval.toLong()
    }

    val N = input().toInt()
    val arr = LongArray(N) {input()}

    arr.sort() // 정렬
    
    var min = Long.MAX_VALUE
    var result = LongArray(3)
    
    // i번째 용액 고정
    for (i in 0 until arr.size-2) {
        val standard = arr[i]

        var left = i+1
        var right = arr.size-1

        // 나머지 2개의 용액 투 포인터로 찾음
        while (left < right) {
            val sum = arr[left] + arr[right]
            
            // 0에 더 가까운 경우 갱신
            if (Math.abs(sum + standard) < min) {
                result[0] = standard
                result[1] = arr[left]
                result[2] = arr[right]
                min = Math.abs(sum + standard)
            }

            if (sum + standard < 0) {
                left++
            } else {
                right--
            }

            if (min == 0L) {
                print(result.joinToString(" "))
                return
            }
        }
    }
    print(result.joinToString(" "))
}