백준 온라인 저지, 이진 탐색/13423번: Three Dots(파이썬)

문제

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

 

문제 정의

직선 위에 서로 다른 N개의 점이 찍혀 있다. 점 i의 위치는 Xi이다. N개의 점 중 3개를 골라 가장 왼쪽에 있는 점을 a, 가운데 있는 점을 b, 가장 오른쪽에 있는 점을 c라고 하자. 각각의 점의 위치는 Xa, Xb, Xc이다. 이때 점 a, b 사이의 거리와 점 b, c사이의 거리가 같으면 세 점의 간격이 같다고 한다. 즉, Xb - Xa = Xc – Xb일 때 세 점의 간격이 같다. 다음은 N = 5인 경우의 예시이다.

위 예시에서 점의 위치는 각각 -4, -1, 0, 2, 4이다. 이중 -4, -1, 0위치의 세 점을 각각 a, b, c라고 하면 Xb - Xa = 3, Xc – Xb = 1로 간격이 같지 않다. 그러나 -4, -1, 2 위치의 세 점을 각각 a, b, c라고 하면 Xb - Xa = 3, Xc – Xb = 3으로 세 점의 간격이 같다. 위 예시에서 간격이 같은 세 점 a, b, c로 가능한 경우는 (-4, -1, 2), (-4, 0, 4), (0, 2, 4)의 3가지가 있다. N개의 점의 위치가 주어졌을 때, 간격이 같은 세 점으로 가능한 경우가 모두 몇 가지 있는지 출력하는 프로그램을 작성하시오.

 

 

 

입력

첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 다음 줄부터 차례로 T개의 테스트 케이스가 주어진다. 각각의 테스트 케이스의 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,000)이 주어진다. 테스트 케이스의 둘째 줄에는 N개의 점의 위치 X1, X2, X3 … Xn이 차례로 주어진다. 모든 점의 위치는 -100,000,000이상 100,000,000이하의 정수이다.

 

 

출력

각 테스트 케이스의 답을 순서대로 출력한다. 각 테스트 케이스마다 첫째 줄에 간격이 같은 세 점 a, b, c로 가능한 경우의 수를 출력한다.

 

 

예제 입력 1

2
5
2 0 -4 -1 4
5
1 3 2 5 4

 

예제 출력 1

3
4

 

 

접근 방법

- 주어진 점들을 두개씩 탐색하면서 정확히 절반이 되는 값이 주어진 점들 가운데에 있는 지 확인한다.
- 해당 문제의 시간 복잡도 : O(N^2 * logN) = 최대 약 1000만번 연산

 

코드 

# 접근방법
# 주어진 점들을 두개씩 탐색하면서 정확히 절반이 되는 값이 주어진 점들 가운데에 있는 지 확인한다.
# 해당 문제의 시간 복잡도 : O(N^2 * logN) = 최대 약 1000만번 연산

from bisect import bisect_right, bisect_left
import sys

def check_dot(dots, dot):
    right_index = bisect_right(dots, dot)
    left_index = bisect_left(dots, dot)
    if right_index == left_index:
        return 0
    return 1


t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    dots = list(map(int, sys.stdin.readline().split()))
    dots.sort()
    count = 0
    for i in range(len(dots)):
        for j in range(i+2, len(dots)):
            if (dots[i] + dots[j]) % 2 == 0:
                dot = (dots[i] + dots[j]) // 2
                count += check_dot(dots, dot)
    print(count)