[백준 문제풀이] 얼렁뚱땅 10800번 컬러볼 풀다 말기

이유 : 이진탐색을 써봐서 ㅎ

 

비록 시간초과가 떠서 매우 슬프지만

그래도 이진탐색을 넣어봤다는 것에 의의를 두는 편

 

일부러 구글링해도 코드를 아주 깊게 보지 않고 힌트만 얻으려고 하는데

지금 코드의 문제는 O(n^2) 계산 복잡도여서 문제인 듯하다

그래도 최대한 많이 안돌게 할려고 이진탐색 쓴거엿는데

Sum때문에 그런가 ? ㅜ 

 

나는 잘 모르겠고~~~~~~~~~~

 

 

import sys


n = int(sys.stdin.readline())
array = [list(map(int, sys.stdin.readline().split())) for i in range(n)]

for i in range(len(array)) :
	sum = 0
	temp_array = sorted(array, key=lambda x:x[1])
	start = 0
	end = len(temp_array)-1
	index = -1
	while start<=end :
		mid = (start+end)//2
		if array[i][1]>temp_array[mid][1] :
			start = mid + 1
			index = mid
		elif array[i][1]<=temp_array[mid][1] :
			end = mid - 1
	if index==-1 :
		print(0)
		continue
	for j in range(index+1) :
		if (array[i][0] != temp_array[j][0]) and (array[i][1]!=temp_array[j][1]) :
			sum+=temp_array[j][1]
	print(sum)