두 용액

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. 완전탐색으로 각각 차이를 구하여 0에 가까운지 검사하면 O(100,000 * 100,000)의 시간복잡도를 소요하게 됨
2. 따라서 먼저 배열을 정렬한 후, 0번 숫자부터 해당 숫자의 반대 부호(1인 경우 -1, -1인 경우 1) 숫자와 차이가 작은 숫자를 이진탐색을 통해 찾아야 함
3. 배열의 원소의 값이 10억이므로 안전하게 Int64 자료형으로 처리를 해줄 수 있음
4. 현재 숫자의 반대 부호 숫자보다 중간 값이 작은 경우 start를 옮기고, 크거나 같은 경우에는 end를 옮겨 투 포인터가 맞붙었을 때,
5. start와 현재 숫자의 차이(절대값)와 end와 현재 숫자의 차이(절대값)이 더 작은 수를 반환하여 각각을 배열에 저장함
6. 원래의 배열과 이진탐색을 통해 얻어낸 배열의 합의 절대값에서 최소값의 index를 찾아 오름차순으로 출력함으로써 문제를 해결함

5. 전체 코드

//MARK: - 두 용액

//MARK: - Framework
import Foundation

//MARK: - Function
func getAbs(_ number: Int64) -> Int64 {
    return number < 0 ? number * -1 : number
}

func binarySearch(_ array: [Int], _ start: Int, _ end: Int, _ value: Int) -> Int {
    if start + 1 >= end {
        return getAbs(Int64(array[start] - value)) < getAbs(Int64(array[end] - value)) ? array[start] : array[end]
    }
    
    let mid: Int = (start + end) / 2
    return array[mid] < value ? binarySearch(array, mid, end, value) : binarySearch(array, start, mid, value)
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    guard let inputArray: [String] = readLine()?.components(separatedBy: " ") else { return }
    
    let array: [Int] = inputArray.map { Int($0) ?? 0 }.sorted { $0 < $1 }
    var A: [Int] = []
    var B: [Int] = []
    var min: Int64 = 0
    var minIndex: Int = 0
    
    //MARK: - Process
    for i in 0..<N - 1 {
        A.append(array[i])
    }
    
    for i in 0..<N - 1 {
        B.append(binarySearch(array, i + 1, N - 1, A[i] * -1))
    }
    
    min = getAbs(Int64(A[0] + B[0]))
    for i in 1..<N - 1 {
        if min > getAbs(Int64(A[i] + B[i])) {
            min = getAbs(Int64(A[i] + B[i]))
            minIndex = i
        }
    }
    
    //MARK: - Output
    print(A[minIndex] < B[minIndex] ? "\(A[minIndex]) \(B[minIndex])" : "\(B[minIndex]) \(A[minIndex])")
}
solution()

전체코드는 여기에서 확인할 수 있습니다.