[BOJ / Swift] 13423 - Three Dots

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

13423번: Three Dots

* 한 게시글에 코드블럭 언어를 하나로 통일해야 하나봐요ㅜㅜ Swift 외 코드는 하이라이트가 정상적이지 않을 수 있습니다..

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)

 

* 개인 블로그에 작성한 내용을 복사해왔습니다.