[Algorithm🧬] 백준 2428 : 표절

문제

처음에는 0.9~1.0 사이에 있는 숫자 개수를 구하고 각각 비교하려고 했는데,
그렇게 하면 이미 비교된 것이 또 포함되어서 비교하는 경우가 생김.
-> 현재 것을 기준으로 0.9 미만인 것을 버리고, 0.9 이상 ~ 현재 것 까지 한번씩만 비교,
그리고 index 더해가면서 똑같이 반복. 그러면 중복 cnt 없이 셀 수 있음.

import sys

readl = sys.stdin.readline

# 넣은 숫자부터 0.9 ~ 1.0 사이에 있는 것을 다 검사하고,
def leftLimit(num):
    left = 0
    right = num - 1

    sol = -1

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

        if files[mid] < 0.9 * files[num]:
            left = mid + 1
            sol = mid
        else:
            right = mid - 1


    return sol + 1


n = int(readl())
files = list(map(int, readl().split()))

files.sort()

sum = 0

for i in range(1, n):
    start = leftLimit(i)
    sum += (i - start)


print(sum)

bisect 이용

n = int(readl())
files = list(map(int, readl().split()))

files.sort()

sum = 0

for i in range(1, n):
    start = leftLimit(i)
    # 정렬된 배열에서 0.9 * files[i] 가 들어갈 가장 왼쪽 자리를 찾는다.
    # start = bisect.bisect_left(files, files[i] * 0.9, 0, i)
    sum += (i - start)


print(sum)