[백준 2470] 두 용액

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

✍️ 첫번째 접근

이 문제는 전형적인 Parametric Search 유형 문제이다. 이분 탐색은 주어진 값 중에서 원하는 값을 찾는 것이 목적이라면, Parametric Search는 주어진 범위 내에서 원하는 조건 중 가장 최적화된 값을 찾는 것이 목적이다.
문제에서 요구하는 것이 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 찾는 것이 목적이니 Parametric Search로 풀 수 있다고 생각하였다.
예제를 통한 필자의 논리는 이러하였지만 틀린 결과를 받게 되었다.

import Foundation

let n = Int(readLine()!)!
let arr =  readLine()!.split(separator: " ").map{Int(String($0))!}.sorted()
var start = 0, end = n-1
var sum = 0x3f3f3f3f
var answer: (first: Int, second: Int) = (0,0)
while start < end {
    if abs(arr[start] + arr[end]) < sum {
        sum = arr[start] + arr[end]
        answer.first = arr[start]
        answer.second = arr[end]
        start += 1
    }
    else {
        end -= 1
    }
}
print("\(answer.first) \(answer.second)")

✍️ 두번째 접근

예제는 운좋게도 통과하였지만 sum을 기준으로 start와 end의 값을 바꾸는 것이 아니라 start와 end에 있는 특성값의 절댓값을 기준으로 start, end의 값을 바꿔야 함을 다음 반례를 통해 알게 되었다.

5
1 2 3 4 5

또한, 특성값의 범위를 생각하면 -1,000,000,000 이상 1,000,000,000 이하이므로 sum의 초기값을 0x3f3f3f3f가 아닌 더 큰 수로 지정해주어 해결할 수 있었다.

import Foundation

let n = Int(readLine()!)!
let arr =  readLine()!.split(separator: " ").map{Int(String($0))!}.sorted() // 용액의 특성값을 정렬하며 저장
var start = 0, end = n-1    // 시작과 끝을 지정
var sum = UInt.max  // 용액의 범위를 생각하여 최댓값 설정
var answer: (first: Int, second: Int) = (0,0)
while start < end {
    if abs(arr[start] + arr[end]) < sum {
        sum = UInt(abs(arr[start] + arr[end]))  // sum 갱신
        // 출력해야 하는 답을 저장
        answer.first = arr[start]
        answer.second = arr[end]
    }
    if abs(arr[start]) > abs(arr[end]) {    // 절댓값을 기준으로 하여 start 위치에 존재하는 특성값이 더 크다면 start를 오른쪽으로 한칸 이동
        start += 1
    }
    else {  // 반대라면 end를 왼쪽으로 한칸 이동
        end -= 1
    }
}
print("\(answer.first) \(answer.second)")