workspace/algorithm
[이분탐색 / python] 13423. Three Dots
HwangJerry
2023. 3. 31. 00:35
https://www.acmicpc.net/problem/13423
13423번: Three Dots
직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는
www.acmicpc.net
문제 분석
우선 탐색을 해야 하는 문제이다. 이진 탐색에 대한 이야기해보면 필요 없는 범위에 대한 탐색을 막음으로서 탐색을 좀 더 빠르게 수행하는 방법이다. 보통 O(logN)을 갖는다.
"""(이진탐색) 첫 번째 풀이-시간초과"""
t = int(input())
for i in range(t):
n = int(input())
li = sorted(list(map(int, input().split())))
# print(li)
ans = 0
for i in range(len(li)-2):
for j in range(i+2, len(li)):
if li[i] != li[j]:
mid = (li[i]+li[j])//2
flag = (li[i]+li[j])%2
# print(li[i],mid, li[j])
if mid in li and not flag: ans += 1
print(ans)
"""(이진탐색) 두 번째 풀이-성공"""
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n = int(input())
li = sorted(list(map(int, input().split())))
ans = 0
for i in range(len(li)-2):
for j in range(i+2, len(li)):
left = i
right = j
target = (li[left]+li[right]) / 2
while left <= right:
mid_idx = (left + right) // 2
if li[mid_idx] == target: ans += 1; break
elif li[mid_idx] < target: left = mid_idx+1
elif li[mid_idx] > target: right = mid_idx-1
print(ans)