[BOJ] 2470 두 용액

21 May 2022

Reading time ~2 minutes

두 용액

링크: https://www.acmicpc.net/problem/2470

입력을 양수와 음수 따로 저장한다.
그 후 음수들에 대해서 그에 대응하는 양의 정수 중 같은 값이면 좋고, 없다면 그와 유사한 값들을 찾는다.
유사한 값을 찾기 위해서 이분 탐색이 용이할 것 같아 이를 이용했다.
그 후 유사한 값들에 대해 이전 해당 인덱스 이전, 다음 값들을 비교해서 그 차가 더 적은 값들을 찾아 차이가 최소가 되는 값을 찾는다.

처음 입력받았을 때 양의 정수만 또는 음의 정수만 입력받았을 때를 대비해 음의 정수일 경우 그 값이 가장 큰 2개의 합, 양의 정수일 경우 그 값이 가장 작은 2개의 합을 최소값으로 저장하여 출력한다.

정답 코드

class Boj2470 {
    companion object{
        var pair = Pair(-1, -1)
        var ans = Pair(-1, -1)
        var minVal = Int.MAX_VALUE
        val minusList = mutableListOf<Int>()
        val plusList = mutableListOf<Int>()

        fun binarySearch(minusIdx: Int): Int {
            val target = minusList[minusIdx].absoluteValue

            var low = 0
            var high = plusList.lastIndex
            var mid = 0

            while (low <= high) {
                mid = (low + high) / 2

                when {
                    plusList[mid] == target -> break
                    plusList[mid] > target -> high = mid - 1
                    else -> low = mid + 1
                }
            }
            if(plusList[mid] > target && mid > 0){
                if((plusList[mid-1] - target).absoluteValue < (plusList[mid] - target).absoluteValue)
                    mid -= 1
            }
            else if(plusList[mid] < target && mid < plusList.lastIndex){
                if((plusList[mid+1] - target).absoluteValue < (plusList[mid] - target).absoluteValue)
                    mid += 1
            }

            val gap = (plusList[mid] - target).absoluteValue
            if(minVal > gap){
                minVal = gap
                ans = Pair(minusList[minusIdx], plusList[mid])
            }

            return -1
        }
        @JvmStatic
        fun main(args: Array<String>){
            val n = readln().toInt()
            val d = readln().split(' ')
            d.forEach {
                val int = it.toInt()
                if(int < 0) minusList.add(int)
                else plusList.add(int)
            }

            if(plusList.size > 1) {
                plusList.sort()
                ans = Pair(plusList[0],plusList[1])
                minVal = plusList[0] + plusList[1]
            }
            if(minusList.size > 1) {
                minusList.sort()
                val first = minusList[minusList.lastIndex-1]
                val second = minusList[minusList.lastIndex]
                if(minVal > (first+second).absoluteValue) {
                    ans = Pair(first, second)
                    minVal = (first+second).absoluteValue
                }
            }

            if(minusList.isNotEmpty() && plusList.isNotEmpty())
                for(i in 0..minusList.lastIndex) binarySearch(i)

            println("${ans.first} ${ans.second}")
        }
    }
}