[백준(BOJ)] 9024 두 수의 합 - 스위프트 (Swift)
[Gold V] 두 수의 합 - 9024
성능 요약
메모리: 122436 KB, 시간: 508 ms
분류
이분 탐색, 정렬, 두 포인터
제출 일자
2024년 1월 21일 16:49:00
문제 설명
여러 개의 서로 다른 정수 S = {a1, a2, …, an} 와 또 다른 정수 K 가 주어졌을 때, S 에 속하는 서로 다른 두 개의 정수의 합이 K 에 가장 가까운 두 정수를 구하시오. 예를 들어, 10 개의 정수
S = { -7, 9, 2, -4, 12, 1, 5, -3, -2, 0}
가 주어졌을 때, K = 8 에 그 합이 가장 가까운 두 정수는 {12, -4} 이다. 또한 K = 4 에 그 합이 가장 가까운 두 정수는 {-7, 12}, {9, -4}, {5, -2}, {5, 0}, {1, 2} 등의 다섯 종류가 있다.
여러 개의 서로 다른 정수가 주어졌을 때, 주어진 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수에 가장 가까운 두 정수의 조합의 수를 계산하는 프로그램을 작성하시오.
입력
프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄에 한 개의 테스트 케이스에 해당하는 데이터가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 개의 정수 n 과 K (2 ≤ n ≤ 1,000,000, -108 ≤ K ≤ 108 )가 한 개의 공백을 사이에 두고 입력된다. 두 번째 줄에는 n 개의 정수가 하나의 공백을 사이에 두고 주어지며, 각 정수의 최댓값은 108 이고, 최솟값은 -108 이다. 잘못된 데이터가 입력되는 경우는 없다.
출력
출력은 표준출력(standard output)을 사용한다. 입력되는 테스트 케이스의 순서대로 다음 줄에 이어서 각 테스트 케이스의 결과를 출력한다. 각 테스트 케이스의 출력되는 첫 줄에 입력으로 주어진 n 개의 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수 K 에 가장 가까운 두 정수의 조합의 수를 출력한다.
풀이
위 문제는 두 수의 합이 K에 가까운 정수의 조합을 구하는 문제이기 때문에, 두 개의 포인터를 사용하여 문제를 해결할 수 있었습니다.
배열을 정렬하고, 양 끝을 포인터로 지정해둡니다. 해당 포인터들을 움직이면서 조건에 맞는 값을 찾아나가는 방식을 사용하였습니다.
첫 번째는 |K - (두 수의 합)|이 최소값인지에 대한 여부를 확인하였습니다.
만약 기존의 값보다 작다면, 최소값을 갱신하고, 해당 쌍의 개수를 1로 초기화해주고, 기존의 값과 같다면 해당 쌍의 개수를 1 더해줍니다.
두 번째로 확인할 점은 두 수의 합이 K보다 작다면 값 두 수의 합이 더 커야하기 때문에 왼쪽에 있는 포인터를 오른쪽으로 한 칸 이동시켜주고, K보다 크거나 같으면 두 수의 합을 줄여주어야 하기 때문에 오른쪽에 있는 포인터를 왼쪽으로 한 칸 이동시켜줍니다.
위의 계산을 통해 얻은 쌍의 개수를 출력해주면 되는 문제입니다.
하지만 해당 문제를 일반적인 입출력을 받게 되면 시간초과가 나타납니다. (처음엔 다른 방법으로 풀어야되나 싶었는데 찾아보니 다른 언어로는 위의 방식대로 하면 잘 풀리더라고요,,)
이를 fileIO를 통해 입력값을 받아오면 문제를 해결할 수 있었습니다.
다음은 코드입니다.
import Foundation
final class FileIO {
private let buffer:[UInt8]
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer[index]
}
@inline(__always) func readInt() -> Int {
var sum = 0
var now = read()
var isPositive = true
while now == 10
|| now == 32 { now = read() } // 공백과 줄바꿈 무시
if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
while now >= 48, now <= 57 {
sum = sum * 10 + Int(now-48)
now = read()
}
return sum * (isPositive ? 1:-1)
}
@inline(__always) func readString() -> String {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
}
@inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return Array(buffer[beginIndex..<(index-1)])
}
}
let file = FileIO()
let t = file.readInt()
for _ in 0..<t {
let nk = (file.readInt(), file.readInt())
var integers = [Int]()
for _ in 0..<nk.0 {
integers.append(file.readInt())
}
integers.sort()
var (left, right) = (0, integers.count - 1)
var (minAbs, count) = (abs(nk.1 - (integers[left] + integers[right])), 0)
while left < right {
let sum = integers[left] + integers[right]
let diff = abs(nk.1 - sum)
if diff < minAbs { // 절대값의 최소 갱신이 필요하면
minAbs = diff
count = 1
} else if minAbs == diff { // 절대값의 최소값이 나온다면
count += 1
}
if sum < nk.1 {
left += 1
} else {
right -= 1
}
}
print(count)
}