[Python] 2428번 표절

✏️ 문제

문제 파악

이분 탐색으로 안풀면 시간 초과가 뜬다.

 

알고리즘

• 정렬
• 이분 탐색

 

 

코드

• 이분 탐색 안쓰고 풀 때 시간 초과 코드

import sys
input = sys.stdin.readline

n = int(input())
files = sorted(list(map(int, input().split())))

cnt = 0
for i in range(n-1):
  for j in range(i+1, n):
    if files[i] <= files[j] and files[i] >= 0.9 * files[j]:
      cnt += 1
      
print(cnt)

• 이분 탐색 사용

import sys
input = sys.stdin.readline

n = int(input())
files = sorted(list(map(int, input().split())))

cnt = 0
for i in range(n):
  start, end = i, n-1
  
  while start <= end:
    mid = (start + end) // 2

    if files[i] >= 0.9 * files[mid]:
      start = mid + 1
    else:
      end = mid - 1
  
  cnt += start - i - 1
print(cnt)