문제
https://www.acmicpc.net/problem/2470
입력
n: Int = 전체 용액 수
arr: [Int] = 용액 특성 값
2 <= n <= 100,000
-10억 <= arr[i] <= 10억
결과
ans: (Int,Int) = 두 용액의 합이 0에 가까운 조합
해석
두 용액이라는 말과 n의 길이가 십만 정도인 걸 보면
정렬 후 투포인터로 찾아가면 될 것 같다
- 두 용액의 합이 현재 gap보다 작으면 업데이트
- 두 용액의 합이 음수일 경우 left를 오른쪽으로 두 용액의 합이 양수일 경우 right를 왼쪽으로 이동시키면 될 듯하다.
코드
import Foundation
let n = Int(readLine()!)!
let arr = readLine()!.split{$0 == " "}.map{Int($0)!}.sorted()
var left = 0
var right = n-1
var dist: Int = Int.max
var ans: (lq1: Int ,lq2: Int) = (0,0)
while left < right {
let l = arr[left]
let r = arr[right]
let sum = l+r
if abs(sum) < dist {
dist = abs(sum)
ans = (lq1: l, lq2: r)
}
if sum < 0 {
left += 1
} else {
right -= 1
}
}
print(ans.0, ans.1)
'PS > 백준' 카테고리의 다른 글
[백준] 1450 냅색문제 (0) | 2024.10.15 |
---|---|
[백준] 1806 부분합 (0) | 2024.10.14 |
[백준] 3273 두 수의 합 (0) | 2024.10.14 |
[백준] 1202 보석 도둑 (0) | 2024.10.14 |
[백준] 15486 퇴사 2 (0) | 2024.10.13 |