[실버 2] 백준 13423 - Three Dots

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

풀이

다음 조건을 만족하는 수열 내 세 수 a, b, c의 개수를 찾는것이다.

1. a < b < c
2. b - a = c - b, 즉 등차수열 (공차 일정한 수열)

• 정렬된 수열 A에서 두 수 A[i], A[j]를 선택하고, 공차를 구해서 등차수열의 세 번째 수 c = 2 * A[j] - A[i]가 A에 존재하는지를 판단한다.
• A는 정렬되어 있지만, 존재 여부를 빠르게 체크하기 위해 set으로도 관리한다.
• a < b < c의 조건을 만족시키기 위해 i < j로만 이중 루프를 돌린다.

코드

# 백준 13423 - Three Dots
# 분류 : 자료구조

T = int(input())
for _ in range(T) :
    N = int(input())
    A = list(map(int, input().split()))
    S = set(A)

    A.sort()
    count = 0
    for i in range(N) :
        for j in range(i + 1, N) :
            if 2 * A[j] - A[i] in S :
                count += 1
    
    print(count)