[백준 2473] - 세 용액(Kotlin)[골드3]

문제

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

2473번: 세 용액

 

문제 풀이

투 포인터 알고리즘의 대표적인 예시 문제라고 할 수 있습니다.

https://jja2han.tistory.com/284

투 포인터 알고리즘(Two Pointer)

투 포인터 알고리즘에 대해서 모르시다면 한번 읽고 오시면 도움이 됩니다.

두 용액과 다르게 세 가지 용액이라서 탐색을 어떻게 투 포인터 알고리즘을 사용해야 할까에 대해서 고민을 할 수 있습니다.

간단하게 하나를 고정시켜두고, 나머지 용액을 탐색해서 0에 가장 가까운 합을 찾아내는 경우의 수를 출력하면 됩니다.

요약하면

두 용액과 다른 점은 세 가지 용액이라는 점을 용액 하나를 고정시켜 두고, 나머지를 탐색한다.

탐색범위를 조절하는 과정은

세 용액의 농도 합이 0보다 작다면 왼쪽 범위를 한 칸 증가시켜주고, 0보다 크다면 오른쪽 범위를 한칸 감소시켜 줍니다.

절댓값을 비교해서 0에 가장 가까운 값으로 업데이트하지만, 0을 찾았다면 그 직후 종료하고 출력합니다.

0을 찾을 경우 많은 경우의 수가 있더라도 하나만 출력해도 허용되기 때문에, 굳이 여러 번 탐색할 필요가 없습니다.

 

 

 

전체 코드

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

class `2473` {
    private var n = 0
    private lateinit var list : Array<Long>
    private val br = BufferedReader(InputStreamReader(System.`in`))
    private lateinit var answer : Triple<Long,Long,Long>
    var sum = 3000000001
    init{
        input()
    }
    fun input(){
        n= br.readLine().toInt()
        list = Array(n){0L}
        val inputs = br.readLine().split(" ")
        for(i in 0 until n ){
            list[i] = inputs[i].toLong()
        }
        list.sort()
        for(i in 0 until n-2){
            if(sum==0L)
                break
            search(i)
        }
        println("${answer.first} ${answer.second} ${answer.third}")
    }
    fun search(start : Int){
        var end = n-1
        var mid = start+1
        while(mid<end){
            val result  = list[start] + list[mid] + list[end]
            if(abs(sum)>abs(result)){
                answer = Triple(list[start],list[mid],list[end])
                sum = result
            }
            if(result<0) {
                mid++
            } else {
                end--
            }
        }
    }
}
fun main() {
    val solution = `2473`()
}