[Swift] 프로그래머스 코딩테스트 연습> 연습문제 > 점 찍기

 

 

풀이

0부터 d만큼의 이중 포문으로 구현을 했으나 d의 최댓값이 백만이면 시간 복잡도가 백만의 제곱이 되어버린다...시간초과 발생

 

점의 위치가 거리 d 만큼의 길이 내에 있어야 한다.

 

피타고라스 정의 d^2 = x^2 + y^2 를 이용하면 두개만 알면 나머지 하나를 구할 수 있다.

d는 기본 값으로 주어지고 x는 포문으로 값을 받으면 단일 포문으로 y를 구할 수 있게 된다.

 

sqrt(d^2 - x^2)은 y의 최댓값이 되고 y또한 k의 배수이기 때문에 k만큼 나누어 갯수를 구한다.

 

 

코드

 

func solution(_ k:Int, _ d:Int) -> Int64 {
    var count: Int64 = 0
    let result = d * d
    for i in stride(from: 0, through: d, by: k){
        let x = i * i
        count += Int64(Int(sqrt(Double(result - x))) / k + 1)        
    }
    return count
}