[백준] (Swift) 2110번 - 공유기 설치 (골드4, 이분탐색)

⚫️ 문제 

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

⚫️ 나의 풀이

◾️ 처음에 생각한 풀이

어떤 것을 기준으로두고 탐색할것인가가 고민스러웠던 문제였다. 처음에 무작정 생각한 풀이 방식은, C개의 공유기를 설치해야하니, N개의 집에서 C개의 집을 고르는 모든 조합을 고려한 뒤 거리를 볼끼? 싶었는데 ㅋㅋㅋㅋ 말도 안됐다. 주어진 조건을 보자

입력 조건은 이렇다. 일단 집은 최대 10억개가 주어질 수 있기 때문에, 시간초과가 나는게 당연해보였다.

◾️ 그럼 어떤 것을 기준으로 두고 탐색해야하지? 

공유기를 설치해야하고, 그 거리를 고려해야하는데 어떤 것을 기준으로 두고 탐색해야하는지 오랫동안 헤맸다. 인터넷의 조금의 도움을 얻은 결과, '거리'를 기준으로 탐색을 진행하면 됐다. 

5 3
1
2
8
4
9

백준에서 주어진 예제를 기준으로 살펴보자. 우선, 집들은 일직선으로 이루어져 있어서 각 집마다 최소 거리는 1이다. 그리고, 주어진 예제에서는 최고 거리는 첫번째집과 마지막집의 거리인 8이 될 것이다. 

◾️ 가장 첫번재로 든 생각은, 선형탐색으로 진행하는것 

거리가 1일 때, 2일때, 3일 때,,,, 이렇게 탐색을 진행해서 총 C개의 공유기를 설치할 수 있다면? 정답으로 출력하면 되겠다.

이렇게 풀어도 문제는 풀릴것이다. 하지만, 우리에겐 입력 조건이 주어졌다. 이렇게 하게 되면, O(N^2)의 시간복잡도를 가지게 될텐데, 우리는 총 N을 10억까지 입력받을 수 있으므로,, 이렇게 선형탐색으로 진행하는 방식은 사용할 수 없다.

◾️ 거리를 기준으로 이분탐색으로 풀어야한다

우리는 시간복잡도를 줄이기 위해서 이분탐색을 진행해야한다. 그럼 어떤 것을 기준으로 left, right, mid를 설정할까? 앞에서 말했듯, 이것을 고민하는데 가장 오랜시간을 할애했고, 결국,, 인터넷의 도움을 조금 받았다. (또 막상 도움받으니까 왤케 쉽냐.. 내 생각은 왤케 짧은것인가? ㅜㅜ)

앞에서 말했듯, left는 해당 집들 사이의 가장 최단거리 1, right는 현재 입력받은 집들 사이에서 최대가 될 수 있는 값으로 설정할 수 있다. 아래와 같은 순서대로 코드를 구현할 수 있을 것 같다.

• 이분탐색은 오름차순을 기준으로 진행 -> home 리스트를 오름차순 정렬 해주어야 함
• left 와 right설정
• mid는 ( left + right ) / 2 로 설정한 뒤
• home 리스트 맨 앞 부터 mid 간격 이상일 경우 공유기 설치, 설치된 home 갯수 cnt
  (mid 간격 이상일 경우 설치하는 이유는, 최소! mid만큼 떨어져있다는 뜻이기 때문)
• 설치된 공유기 갯수가 c보다 작다면, mid 가 너무 넓다는 뜻 -> mid를 줄여주어야함 (right를 left쪽으로 옮겨야 mid가 줄어듬)
• 설치된 공유기 갯수가 c보다 크다면, mid가 너무 좁다는 뜻 -> mid를 넓혀주어야함 (left를 right쪽으로 옮겨야 mid가 커짐)

 

이렇게 코드를 진행시켜주면 되겠다. 이분탐색 특성상, '위치'를 기반으로 많이 코드를 작성했었는데 이렇게 거리를 기준으로 코드를 작성하니까 mid를 넓힌다, 줄인다에 대한 개념이 애매했고 생각해내기 조금 힘들었던 것 같다. 

 

⚫️ 정답코드

import Foundation

let nc = readLine()!.split(separator: " ").map{ Int($0)! }
let n = nc[0]
let c = nc[1]
var home = [Int]()

for _ in 0..<n {
    home.append(Int(readLine()!)!)
}
home.sort()

var left = 1
var right = home[home.count - 1] - home[0]
var answer = -999

while left <= right {
    var start = home[0]
    var cnt = 1
    let mid = (left + right) / 2

    // mid 기준으로 home 리스트 돌면서 공유기 설치 가능한지 확인
    for i in 0..<n {
        let d = home[i] - start
        // mid보다 커야 공유기 설치 가능
        if mid <= d {
            cnt += 1
            start = home[i]
        }
    }

    // 범위를 어떻게 줄여나가는거야?
    // let mid = (left + right) / 2
    // 공유기가 넘 많으면 -> mid를 넓혀야해 mid를 넓힐라면? left를 right쪽으로 가야 mid가 커짐
    // 공유기가 넘 적으면 -> mid를 줄여야해 mid를 줄일라면? right를 left쪽으로 가줘야 mid가 작아짐
    if c <= cnt {
        answer = mid
        left = mid + 1
    } else {
        right = mid - 1
    }
}

print(answer)