3020. 개똥벌레

문제링크

난이도	정답률(_%)
Gold V	40.000%

메모리 (KB)	시간 (ms)
154292	536

설계

1. 석순과 종유석을 두개의 list로 분리해서 입력을 받는다.
2. 이분탐색을 위해 각각 오름차순으로 정렬한다.
3. 동굴의 높이만큼 for 문을 돌면서 모든 층에서의 개똥벌레가 부숴야할 장애물을 센다.
4. 각 층에서 장애물의 갯수를 셀 때, 층에 걸리는 장애물의 크기중 가장 작은 것를 이분탐색을 통해 찾아 그 층에서의 장애물의 갯수를 셀 수 있다.
5. 각 층에서의 장애물의 갯수 중 최솟값과 최솟값의 갯수를 출력한다.

시간복잡도

O(H * logN)

코드

n, h = map(int, input().split())
top = []
bottom = []
for i in range(n):
    if i % 2 == 0:
        bottom.append(int(input()))
    else:
        top.append(int(input()))
top.sort()
bottom.sort()
obstacles = []
for i in range(1, h+1):
    l, r = 0, len(bottom)-1
    bottomCnt = 0
    while l <= r:
        mid = (l+r)//2
        if bottom[mid] >= i:
            bottomCnt = len(bottom) - mid
            r = mid - 1
        else:
            l = mid + 1

    topCnt = 0
    l, r = 0, len(top)-1
    while l <= r:
        mid = (l+r)//2
        if h - top[mid] < i:
            topCnt = len(top) - mid
            r = mid - 1
        else:
            l = mid + 1
    obstacles.append(topCnt+bottomCnt)
res = min(obstacles)
print(res, obstacles.count(res))