2110 - 공유기 설치

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

2110번: 공유기 설치

Binary Search 문제입니다.

최근 면접 준비로 기본적인 알고리즘을 공부하고 있는데, 딱 좋은 알고리즘이 Binary Search 같네요.

마침 제가 Binary Search 문제였다는 것을 알았기에 풀 수 있었던 문제였지만, 그게 아니었다면 Binary Search까지 생각해내기 어려웠을 거 같습니다.

 

왜 Binary Search를 사용하냐면 결국 저희는 서로 인접한 거리 중 최대 거리를 찾는 것입니다. 즉, 답은 무조건 정해져있습니다. 그렇다면 그 문제를 푸는 것보단, 답이 이미 정해져 있다고 가정하고 문제를 해석해보면 어떨까요?

 

그런 발상으로 Binary Search를 사용했습니다. 답이 될 수 있는 가장 큰 값과 작은 값을 뺀 거리를 N과 1 사이엔 무조건 답이 있으니 그 사이에서 답을 찾아보는거죠. 답을 찾는 시간복잡도는 O(logN)이 되겠죠. (순전한 답을 찾는 복잡도입니다. 추가적인 연산으로 그 답이 맞는가, 틀린가가 필요합니다)

 

답을 구했으면 그 답이 가능한지 파악해보고, 설치된 공유기가 적다면 그 거리를 줄여서 공유기를 더 설치를 해야합니다. 왜냐면 저희는 C만큼 공유기를 설치할 것이라고 정해놓았기 때문이죠.

 

설치된 공유기가 C보다 많으면 어떻게 될까요? 그 정답은 진짜 정답이 될 수 있는 후보에 오르게 됩니다. 이런 식으로 Binary Search를 진행하면서 답을 찾아간다면, 최종 답을 구할 수 있습니다.

 

def binarySearch(L, R):
    global N, C, result, answer
    mid = (L + R) // 2
    if L > R: # 이 부분에서 >= 을 사용했는데, >= 을 해버리면 답이 아닌 답도 정답 후보에 오르게됩니다.
        return mid
    cnt = 1
    cur = 0
    nxt = 1
    while True:
        if nxt >= N:
            break
        if arr[nxt] - arr[cur] < mid:
            nxt += 1
            continue
        else:
            cnt += 1
            cur = nxt
            nxt = cur + 1
    if cnt < C:
        return binarySearch(L, mid - 1)
    else:
        answer = mid
        return binarySearch(mid + 1, R)

N, C = list(map(int,input().split()))

arr = []
for _ in range(N):
    num = int(input())
    arr.append(num)

arr.sort()

first = arr[0]
end = arr[-1]

max_ = end - first
min_ = 1
binarySearch(min_, max_)

print(answer)

 다시 한 번 풀어봤는데 더 깔끔한 코드가 나왔네요. 다시보니 비슷한거 같기도 하고..

def binarySearch(minn, maxx):
    global C 
    mid, cur, nxt, cnt  = (minn + maxx) // 2, 0, 1, 1
    if minn > maxx:
        return mid
    
    ou = 0
    # 공유기 갯수 확인
    while 1:
        if cnt > C:
            ou = 1
            break
        elif nxt >= len(arr):
            break
        elif arr[nxt] - arr[cur] >= mid:
            cnt += 1
            cur = nxt
            nxt += 1
        else:
            nxt += 1

    if cnt < C:
        return binarySearch(minn, mid - 1)
    else:
        return binarySearch(mid + 1, maxx)

N, C = list(map(int,input().split()))

arr = []

for _ in range(N):
    num = int(input())
    arr.append(num)

arr.sort()

minn, maxx = arr[0], arr[-1]

print(binarySearch(1, maxx- minn))