백준 파이썬 2428번 : 표절 이진탐색 풀이

https://www.acmicpc.net/problem/2428

2428번: 표절

솔루션 파일의 크기가 a,b,c...로 주어졌을 때 a<=b, a>=b*0.9를 만족하는 문자쌍의 개수를 구해야 하는 문제다 

입력값이 정수라는 데 주의하자. 따라서 리스트를 받을 때 float로 받아줘야 한다 

 

1. 리스트를 입력받아 오름차순으로 정렬해준다. 그러면 모든 요소에 대해 a<=b를 만족한다  

2. 정렬된 리스트가 만약 [a,b,c,d,e]라고 한다면, a와 b,c,d,e를 비교하고 b와 c,d,e를, c와 d,e를, d와 e를 비교해야 한다 

3. n번만큼 반복할 때 left = i, right = n, center = (left+right)//2로 두고 이분탐색을 실시한다 

4. answer에 값을 누적시켜준 뒤에 출력한다. r이 a>=b*0.9를 만족하는 요소의 최대 인덱스를 나타내므로 조건을 만족하는 요소는 총 r-1개가 존재한다. 그리고 자기자신이나 이전에 비교한 값은 제외해야 하므로 i를 뺀 값을 누적시킨다. 

n = int(input())
ary = sorted(list(map(float,input().split())))
answer = 0 
for i in range(n):
    l = i
    r = n
    while l<r:
        c = (l+r)//2
        if ary[i]>=ary[c]*(0.9):
            l = c + 1 
        else:
            r = c 
    answer += r-i-1
print(answer)