Swift 백준 1654 랜선 자르기 (이분탐색)

시간초과 코드

이분 탐색을 사용하지 않으면 다음과 같이 코드를 만들 수 있습니다.

하지만 원하는 값이 나올때까지 모든 모든 경우의 수를 탐색해야 한다는 문제점이 있습니다.

이렇게 코드를 작성하면 시간 복잡도가 O(log n*m) 만큼 나올 수 있으며 이는 시간초과를 일으킵니다.

var line = readLine()!.split(separator: " ").map({Int($0)!})
var arr: [Int] = []
for _ in 1...line[0] {
    arr.append(Int(readLine()!)!)
}

for i in stride(from: arr.max()!, to: 0, by: -1) {
    var count = 0
    for j in arr {
        count += (j / i)
    }
    if count == line[1] {
        print(i)
        break
    }
}

 

 

이분 탐색로 시간초과 해결

1. 이분 탐색이란 찾고 싶은 데이터를 절반으로 나눕니다.
2. 나눠진 절반에서 값을 탐색합니다.
3. 만약 count가 필요한 requiredCount보다 크다면 탐색한 범위가 찾고자하는 값이 포함되지 않다는 것을 의미합니다.
4. 원하는 값이 나올때까지 계속 절반으로 나눈값을 또 절반으로 나눠 탐색합니다.

아래와 같이 시간 복잡도가 O(n log m)의 시간 복잡도를 가지기 때문에 시간초과 문제를 해결할 수 있게 됩니다

 

var line = readLine()!.split(separator: " ").map({Int($0)!})
var arr: [Int] = []
for _ in 1...line[0] {
    arr.append(Int(readLine()!)!)
}

let requiredCount = line[1]
var left = 1
var right = arr.max()!
var result = 0

while left <= right {
    let mid = (left + right) / 2
    var count = 0
    for length in arr {
        count += (length / mid)
    }
    if count >= requiredCount {
        result = mid
        left = mid + 1
    } else {
        right = mid - 1
    }
}

print(result)