백준 2467번 용액
출처 - https://www.acmicpc.net/problem/2467
문제
KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.
산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.
입력
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
출력
첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.
풀이
두 용액을 선택하는 것이므로 for문 2개 돌리면 로직은 간단하지만,
N이 최대 10만개이기 때문에 N^2의 시간복잡도는 시간초과가 날 것 같다.
자료가 특이하게 정렬된 상태로 제공되는 것을 보면, 이진탐색을 활용할 수 있다는 점을 생각할 수 있다.
용액 하나를 선택하고, 이것과 짝을 이루어 0에 가장 가까운 혼합용액을 만들어내는 다른 용액을 이진탐색으로 찾을 수 있을 것 같다.
이 과정을 용액 하나하나에 실행시키면 0에 가장 가까운 혼합용액을 만드는 용액의 쌍을 찾을 수 있다.
용액 하나하나에 대해 (n), 이진 탐색으로 짝을 찾는다 (log n). => nlogn 시간
따라서 시간제한 안에 해결할 수 있다.
또, 정렬된 자료를 가지고 활용할 수 있는게 투포인터 전략이 있다.
용액의 특성값이 단조 증가하고 있으므로, 어떤 용액을 가리키는 포인터를 왼쪽으로 옮기면 무조건 작은 값이고, 오른쪽로 옮기면 큰 값이다
그래서 포인터 하나는 맨 처음 용액, 다른 하나는 마지막 용액을 가리키게 하고
두 용액의 특성 값의 합이 양수라면 마지막 용액을 카리키는 포인터를 왼쪽으로 옮겨서 특성값의 합을 줄여준다.
반대로 두 용액의 특성 값의 합이 음수라면, 첫 번쨰 용액을 가리키는 포인터를 오른쪽으로 옮겨서 특성값의 합을 늘려준다.
이 과정을 첫 포인터와 끝 포인터가 만날 때까지 반복하면, 0에 가장 근접한 수치를 얻을 수 있다.
총 n번 포인터를 움직여야하므로 n 시간으로 풀 수 있다.
코드
이진탐색 코드
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.absoluteValue
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val arr = readLine().split(" ").map { it.toInt() }
var minDiff = Int.MAX_VALUE
var minPair = Pair(0, 0)
for (i in arr.indices) {
var l = i + 1
var r = arr.size - 1
while (l <= r) {
val mid = (l + r) / 2
val temp = arr[i] + arr[mid]
if (temp < 0) {
l = mid + 1
} else {
r = mid - 1
}
if (temp.absoluteValue <= minDiff) {
minDiff = temp.absoluteValue
minPair = Pair(arr[i], arr[mid])
}
}
}
println("${minPair.first} ${minPair.second}")
}투포인터 코드
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.absoluteValue
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val arr = readLine().split(" ").map { it.toInt() }
var minDiff = Int.MAX_VALUE
var minL = 0
var minR = arr.size-1
var l = 0
var r = arr.size-1
while (l<r){
val temp = arr[l]+arr[r]
if (temp.absoluteValue<minDiff) {
minDiff = temp.absoluteValue
minL = l
minR = r
}
if(temp>0) r--
else if(temp<0) l++
else break
}
println("${arr[minL]} ${arr[minR]}")
}결과
위가 투포인터
아래가 이진탐색
거의 같다.
