[BinarySearch] 개똥벌레

코드 출처:blog.naver.com/PostView.nhn?blogId=crm06217&logNo=222023706440&categoryNo=23&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

[백준 3020번] 개똥벌레, 이분 탐색 (Binary Search) 응용 (Python 코드 첨부, 난이도: Gold 5)

Pseudocode를 만들면 좀더 순차적으로 문제접근이 된다는 점을 알게됨

 

이 문제에서는 2개의 array에 대해 각각 BS 수행해야 하고 서로 반대되는 조건이 부여된다는 점이 까다로웠다.

 

또한, BS의 target조건을 어떻게 줄 것인가.

 

---

BS의 target을 높이로 정하고 찾고자 하는 리스트를 정렬한 상태에서 BS를 수행하면 해당 높이의 위치를 찾게 된다.

return 값으로는 idx를 받는게 아니라 개수를 받아야 하기 때문에

리스트에서 target의 idx를 찾은후

return은 (해당 리스트의 길이) - (타겟의 idx+1) 로 해준다. # +1을 하는 이유는 start를 0으로 시작 했기 때문에

---

위아래 2개의 리스트에 대해 BS를 수행해야되기 때문에

"위"에 해당하는 리스트에 대해서는 target을 반대로해서 수행한다.

---

그렇게 2개의 리스트에 대해 BS를 수행해서 나온 결과는

각 리스트에 대해 걸리는 장애물의 개수이고 이걸 합한 후

최솟값이 나올때 까지 각 target에 대해 수행

계속 수행하다가 최솟값이 같다면 cnt += 1해줌

import sys
def Binary_Search_Upper(data_list, x):                  #주어진 list에서 x보다 큰 데이터의 개수를 반환; log n 안에 찾음
    left = 0
    right = len(data_list) - 1
    while left <= right:
        mid = (left + right) // 2
        if data_list[mid] <= x:
            left = mid + 1
        else:
            right = mid - 1
    return len(data_list) - (right + 1)                  #index, 개수 차이 때문에 1 더해줌

input_list = input().split()
N = int(input_list[0])
H = int(input_list[1])
data_down = []
data_up = []
for i in range(N):
    input_list_2 = sys.stdin.readline().split()
    input_num = int(input_list_2[0])
    if i % 2 == 0:              #아래부터 높이 재기
        data_down.append(input_num)
    else:                       #위부터 높이 재기
        data_up.append(input_num)
data_down.sort()
data_up.sort()
ans = N                         #장애물의 최솟값
cnt = 0                         #구간 몇 개 있는지
for h in range(1, H + 1):
    down_num = Binary_Search_Upper(data_down, h - 1)
    up_num = Binary_Search_Upper(data_up, H - h)
    cur_num = down_num + up_num     #현재 mid 값을 기준으로 잘랐을 때의 장애물의 수
    if cur_num < ans:               #새로운 최솟값이 나오면 정답 업데이트; 개수는 1부터 다시 셈
        ans = cur_num
        cnt = 1
    elif cur_num == ans:            #현재 최솟값과 같은 값이 한 번 더 나오면 개수 1 증가
        cnt += 1
print(ans, cnt)

[출처] [백준 3020번] 개똥벌레, 이분 탐색 (Binary Search) 응용 (Python 코드 첨부, 난이도: Gold 5)|작성자 SH