[우선순위큐, 이분탐색] - 가운데를 말해요, 사냥꾼

🕹️ 가운데를 말해요

from sys import stdin as s
import heapq



leftHeap = []
rightHeap = []

s= open('input.txt','rt')


n = int(s.readline())

arr = list(map(int,s.readlines()))


for i in range(n):

    if len(leftHeap) > len(rightHeap):
        heapq.heappush(rightHeap,arr[i])
    else :
        heapq.heappush(leftHeap,-arr[i])

    if len(leftHeap) != 0 and len(rightHeap) != 0 and -leftHeap[0] > rightHeap[0] :
        left = -heapq.heappop(leftHeap)
        right = heapq.heappop(rightHeap)
        heapq.heappush(leftHeap,-right)
        heapq.heappush(rightHeap,left)

    print(-leftHeap[0])

🕹️ 사냥꾼

from sys import stdin as s

s = open('input.txt','rt')

M, N, L = list(map(int,s.readline().split()))

arr = list(map(int, s.readline().split()))

arr.sort()

count = 0

def bina(start,end,bf,af):
    global count
    if start > end:
        return False
    mid = (start+end)//2


    if arr[mid] < bf:
        return bina(mid+1,end,bf,af)
    elif arr[mid] > af :
        return bina(start,mid-1,bf,af)
    else :
        count+=1
        return



for i in range(N):
    x, y = list(map(int,s.readline().split()))
    if y > L :
        continue
    else :
        temp = L-y
        bina(0,len(arr)-1,x-temp,x+temp)



print(count)

처음에 for문으로 했는데 시간초과떠서 해당 범위를 넘겨서 해당 범위안에 속할 때만 카운트하고 범위 벗어나면 이분탐색으로 반복 수를 줄이니까 100점으로 통과했다.

❗️ Tip

코딩테스트 문제를 풀 때 PriorityQueue를 쓰게 되면 PriorityQueue가 연산하는 속도 때문에 시간초과가 뜨기도 한다. 그래서 가급적 Heapq를 쓰자.

브루트 포스 문제 리스트

NO	LV	유형	제목	비고
1655	G2	큐	가운데를 말해요	leftHeap의 루트를 mid로 생각하고 문제를 푸니까 바로 해결되었음 - 다시 풀어 보는게 좋을 듯
2110	G4	이분탐색	공유기 설치	이분탐색으로 직접 공유기를 설치해가면서 찾아야 답이 나옴
2470	G5	이분탐색	두 용액	이분 탐색으로 안 풀고 투 포인터로 품
8983	G4	이분탐색	사냥꾼	처음에 for문으로 풀었다가 60점 받아서 중간 탐색 부분 다시 이분 탐색으로 해결함