[BOJ] 백준 11497 통나무 건너뛰기 풀이 (swift)

통나무 건너뛰기

풀이(그리디)

기존엔 left, right 로 구현해서 가장 높이 차가 최소인 경우를 찾아서 구현을 했는데, 더 좋은 방법이 있어서 가져왔습니다 😄

다른 분들의 아이디어에서 가장 중요한 건, 인접한 두 칸의 통나무는 비교하지 않는 것입니다. 이미 다른 더 큰 차이와 비교했을 때 최댓값에 영향을 주지 않기 때문에 문제에서 요구하는 가장 큰 차이를 구할 때 n 과 n-1 의 통나무는 무시하는 것입니다.

통나무를 오름차순으로 정렬했을 때, 1번 통나무는 가장 작은 값이고, N번 통나무는 가장 큰 값인데, 이런 방식으로 배치하게 되면 결국 인접한 통나무 사이의 가장 큰 차이가 나올 가능성이 있는 것은 두 통나무가 두 칸씩 건너뛰어져 있는 위치입니다.

n-1과 n은 배치에서 바로 옆에 있는 통나무들입니다. 하지만, 이 통나무들의 차이는 n-2와 n의 차이에 비해 항상 작을 가능성이 높습니다.

그럼 2칸보다 3칸이나 4칸으로 비교하는게 더 빠를 수 있지 않냐 라고 생각하실 수도 있는데, 비교하는 논리가 직관적이지 않습니다. 좌우에서 고르게 퍼져나가며 점진적으로 증가하기 때문에, 2칸씩 뛰어넘어 배치하는 것이 중요합니다. left, right 보다 연산이 절반 가량 줄어듭니다.

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)])
    }
}
//Thanks to Rhyno
//위의 FileIO클래스는 Swift 에서 입출력 시간을 줄여주는 코드입니다.
let fileIO = FileIO()
let T = fileIO.readInt()

for _ in 0..<T {
    let N = fileIO.readInt()
    var L = [Int](repeating: 0, count: N)
    for i in 0..<N {
        L[i] = fileIO.readInt()
    }
    L.sort()
    var height = 0
    for i in 2..<N {
        height = max(height, L[i] - L[i - 2]) // 2칸 간격의 높이차 계산
    }
    print(height)
}

읽어주셔서 감사합니다! 오타 및 잘못된 내용은 언제든 댓글 달아주시면 최대한 빠르게 수정하겠습니다!