[백준(BOJ)] 9024 두 수의 합 - 스위프트 (Swift)

[Gold V] 두 수의 합 - 9024

문제 링크

성능 요약

메모리: 122436 KB, 시간: 508 ms

분류

이분 탐색, 정렬, 두 포인터

제출 일자

2024년 1월 21일 16:49:00

문제 설명

여러 개의 서로 다른 정수 S = {a₁, a₂, …, a_n} 와 또 다른 정수 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, -10⁸ ≤ K ≤ 10⁸ )가 한 개의 공백을 사이에 두고 입력된다. 두 번째 줄에는 n 개의 정수가 하나의 공백을 사이에 두고 주어지며, 각 정수의 최댓값은 10⁸ 이고, 최솟값은 -10⁸ 이다. 잘못된 데이터가 입력되는 경우는 없다.

출력

출력은 표준출력(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)
}