BOJ 13423 - Three Dots (Python)

S2, 해시

---

풀이

1. 시간초과

• 그냥 3개의 점을 뽑아서 판단하는 combination로직을 생각했는데 1000개의 점중에서 3개를 뽑는거라 시간초과가 당연하게도 발생했다.

from sys import stdin
from itertools import combinations
T = int(stdin.readline())
for _ in range(T):
    n = int(stdin.readline())
    arr = list(map(int, stdin.readline().split()))
    arr.sort()
    res = 0
    comb = combinations(arr, 3)
    for a, b, c in comb:
        if abs(b - a) == abs(c - b):
           res += 1

    print(res)

---

2. 정답 풀이 - 시간초과 해결을 위해 정답을 찾아보니 딕셔너리를 통해 A와 C의 사이값인 B의 존재 유무를 찾는 방법이 있었다.

from sys import stdin
T = int(stdin.readline())
for _ in range(T):
    n = int(stdin.readline())
    arr = list(map(int, stdin.readline().split()))
    arr.sort()
    res = 0

    dic = dict()
    for num in arr:
        dic[num] = True

    for i in range(n-2):
        for j in range(i + 1, n - 1):
            if arr[j] * 2 - arr[i] in dic:      
            # arr[j]*2 를 C로 보고 B의 유무를 찾는다.
                res += 1

    print(res)

실버 2 라기엔 조금 생각하기 어려웠던 문제