[백준] 2428 표절 - python

문제 링크
https://www.acmicpc.net/problem/2428

시도1.시간초과

n = int(input())
solutions = list(map(int, input().split()))
solutions.sort(reverse=True)
count = 0

for i in range(len(solutions)-1):
  for j in range(i+1, len(solutions)):
    if solutions[i]*0.9 > solutions[j]:
      count += j-i-1
      break
    if j == len(solutions) - 1:
      count += len(solutions)-i-1

print(count)

• 접근방법 : 정렬 + 완전탐색
• 시간복잡도 : O(n²)

시도2. 성공

n = int(input())
solutions = list(map(int, input().split()))
solutions.sort(reverse=True) # 내림차순 정렬
count = 0

for i in range(len(solutions)-1):
  if solutions[i] * 0.9 <= solutions[-1]: # 기준이 되는 수보다 작은 모든 수가 가능한 경우
    count += len(solutions) -1 -i
    continue
  
  start = i + 1
  end = len(solutions) - 1
  
  while start <= end:
    mid = (start + end) // 2
    if solutions[mid] >= solutions[i] * 0.9: # 중간 값이 찾고자 하는 값보다 크면
      start = mid + 1
    else: # 작으면
      end = mid - 1
  count += end - i
print(count)

• 접근방법 : 정렬 + 이진탐색
• 시간복잡도 : O(nlogn)