[Algorithm] BOJ 13423

BOJ 13423번 Three Dots

Intro

처음에는 sort를 한 뒤 nC3으로 3개 조합을 뽑고 x[0]+x[2] = 2*x[1]라는 식을 통해 검증하려 하였으나 시간 초과가 발생하였습니다.
결론적으로 sort를 사용하지 않고 nC2의 조합을 사용하여 시간 초과 문제를 해결했습니다.

Solution

1. 특정 값이 입력받은 점의 리스트 내에 존재하는지 탐색하기 쉽도록 x를 key로 갖고 True를 값으로 가지는 dictionary를 생성합니다.
2. 2중 for문을 통해 nC2의 조합을 구하는 코드를 구현합니다.

// nC2 조합
for i in 0..<n {
	for j in range 1..<n {
		// (i, j)
	}
}

3. 만약 리스트 내에 (i번째 점 + j번째 점) / 2의 값이 존재한다면 둘 사이의 중간 값이 존재하는 것이므로 카운트를 증가시킵니다.
4. 모든 조합을 완료하면 측정된 카운트를 출력합니다.
5. 위 과정을 테스트 케이스 개수만큼 반복합니다.

Code

Swift

import Foundation
let t = Int(readLine()!)!
for _ in 0..<t {
    let n = Int(readLine()!)!
    let x = readLine()!.split(separator: " ").map(){Int($0)!}
    var d = [Double: Bool]()
    var cnt = 0
    for i in x { d[Double(i)] = true } // 1번
    for i in 0..<n { // 2번
        for j in i+1..<n where d[Double(x[i]+x[j])/Double(2)] != nil { // 2-3번
            cnt += 1
        }
    }
    print(cnt)
}

Python

import sys
input = sys.stdin.readline

t = int(input().rstrip())
for _ in range(t) :
    n = int(input().rstrip())
    cnt = 0
    x = list(map(int, input().rstrip().split()))
    d = {i:True for i in x}
    for i in range(n):
        for j in range(i+1, n) :
            if (x[i]+x[j])/2 in d : cnt += 1
    print(cnt)