백준 [2473] kotlin

문제

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

2473번: 세 용액

풀이

투 포인터 문제입니다.

3개의 용액의 합의 절대값이 0과 가장 가까운 3개의 용액을 찾는 문제입니다.

 

3개의 용액을 구하기 위해, 기준이 되는 용액을 하나를 고정하고, 두 용액을 투포인터를 통해 포인터를 이동하며, 

최적의 합을 찾는 것이 핵심입니다.

 

for문을 통해 모든 용액을 기준으로 합니다. 이 때 for문의 범위를 전범위로 하는 것이 아니라, 두가지 용액이 더있으므로 , 전체 크기의 -2 만큼만을 loop 해야합니다.

 

나머지 두개의 용액을 찾는 과정은, 왼쪽과 오른쪽을 기준으로 하여, 3개의 용액의 합이 음수면, 왼쪽 포인터를 더해줌으로써 0과 가까워지게 해주고, 양수인 경우 오른쪽 포인터를 빼줌으로 0과 가까워지도록 합니다.

 

각 이동과정에서 기존의 3개의 용액과 비교하여 최적이라면, 새롭게 갱신을 해줍니다.

 

 

 

코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.abs

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val N = br.readLine().toInt()
    val solid = br.readLine().split(" ").map { it.toLong() } as MutableList
    solid.sort()
    var ans = MutableList<Long>(3){0}
    var ansSum = Long.MAX_VALUE

    for(i in 0 until solid.size - 2){
        var left = i + 1
        var right = solid.size - 1
        while(left < right){
            val ns : Long = solid[i] + solid[left] + solid[right]
            if(abs(ns) < ansSum) {
                ans = mutableListOf(solid[i], solid[left], solid[right])
                ansSum = abs(ns)
            }
            if(ns < 0) left++
            else right--
        }
    }

    bw.write(ans.joinToString(" "))
    bw.flush()
    bw.close()
}