[Algorithm🧬] 정올 2788 : 도약

문제

일단.. 이진 탐색 챕터에 있었어서 그렇게 풀어야겠다고 생각했더니... 아무 생각이 안나서 전체 탐색으로 풀고 나서 다시 생각해봤다.

전체 탐색 코드

import sys

n = int(sys.stdin.readline())
leaves = [int(sys.stdin.readline()) for _ in range(n)]

leaves.sort()

cnt = 0

for i in range(n - 2):
    for j in range(i + 1, n - 1):
    	dist1 = leaves[j] - leaves[i]
        for k in range(j + 1, n):
            dist2 = leaves[k] - leaves[j]

            if dist2 >= dist1 and dist2 <= 2*dist1:
                cnt += 1
            elif dist2 > 2 * dist1:
            	break

print(cnt)

이진 탐색 코드

import sys
# import bisect

# 첫번째와 두번째의 거리인 dist ~ 2*dist 사이에 있는 잎의 위치를 구하기 위해 이진탐색.

# leaf 보다 크거나 같은데 그 중 젤 작은거 index
def lower(start, end, leaf):
    pos = -1
    while start <= end:
        mid = (start + end) // 2

        if leaves[mid] >= leaf:
            end = mid - 1
            pos = mid
        else:
            start = mid + 1

    return pos

# leaf 보다 작거나 같은데 그 중 젤 큰거 index
def upper(start, end, leaf):
    pos = -1
    while start <= end:
        mid = (start + end) // 2

        if leaves[mid] <= leaf:
            start = mid + 1
            pos = mid
        else:
            end = mid - 1

    return pos


n = int(sys.stdin.readline())
leaves = [int(sys.stdin.readline()) for _ in range(n)]

leaves.sort()

cnt = 0

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        dist = leaves[j] - leaves[i]

		# start, end 사이에 있는 것의 개수를 세어야 함.
        start = leaves[j] + dist
        end = leaves[j] + 2 * dist

		
        # start 보다 크거나 같으면서 그 중 젤 작은거 index
        l =  lower(j + 1, n - 1, start)
        if l == -1 or leaves[l] > end: continue
        # end 보다 작거나 같으면서 그 중 젤 큰거 index
        u = upper(l, n - 1, end)

        # 라이브러리가 있지만 상황에 완벽히 맞진 않는듯.. 답이 다르게 나옴 3 1 2 3  같은 케이스
        # l = bisect.bisect_left(leaves, start)
        # u = bisect.bisect_right(leaves, end)

        cnt += u - l + 1

print(cnt)

생각해도 모르겠어서 결국 다른 풀이 참고해서 풀었다.
lower, upper 가 아직도 겁나 헷갈리고... 혼자 짤 수 없을 것 같기 때문에 복습 필수

2트

연잎 2개를 고르고

3개~N개 사이에서 조건을 만족하는 가장 왼쪽, 가장 오른쪽을 구해서 그 사이 개수 count

import sys

readl = sys.stdin.readline

def findThirdLeft(first, second):
    left = second + 1
    right = n - 1

    dist = 연잎[second] - 연잎[first]

    index = -1

    while left <= right:
        mid = (left + right) // 2

        dist2 = (연잎[mid] - 연잎[second])


        if dist <= dist2: # mid 가 너무 큼
            right = mid - 1
            index = mid
        else:
            left = mid + 1

    return index

def findThirdRight(first, second):
    left = second + 1
    right = n - 1

    dist = 연잎[second] - 연잎[first]

    index = -1

    while left <= right:
        mid = (left + right) // 2

        dist2 = (연잎[mid] - 연잎[second])

        if dist2 <= 2 * dist:
            left = mid + 1
            index = mid
        else:
            right = mid - 1


    return index


n = int(readl())
연잎 = [int(readl()) for _ in range(n)]
연잎.sort()

sum = 0

for i in range(n - 2):
    first = 연잎[i]
    for j in range(i, n - 1):
        second = 연잎[j]

        left = findThirdLeft(i, j)
        right = findThirdRight(i, j)

        if left != -1 and right != -1:
            sum += right - left + 1
        
        # 여기도 위에처럼 left 먼저 구하고 right 필요하면 구하는 식으로 할 수 있었을듯.

print(sum)